99클럽 코테 스터디 16일차 TIL / 그리디

✏️ 문제

[백준/BOJ] 2847번: 게임을 만든 동준이(https://www.acmicpc.net/problem/2847)

 

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S4

✅ 소요 시간: 예전에 풀었던 문제라 측정 X

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 유형 파악

예전에 풀 때는 알고리즘을 크게 신경 쓰지 않았었는데 오늘 알고리즘 분류를 보니까 그리디 알고리즘이었다.

 

내가 알고 있는 그리디의 특징은 '매 순간 그 상황에서 최적인 선택을 하지만 전체 결과에서도 그 결과가 최적임을 보장할 수는 없음'인데 이 관점에서 생각했을 때 이 문제가 왜 그리디 알고리즘에 속하지? 싶었다. 챗지피티가 항상 정답만 얘기하는 건 아니지만 이해에 도움이 되고자 살짝쿵 질문한 후 내가 이해한대로 정리해봤다.

---

 

문제의 요구사항

- 필요한 경우 레벨마다 점수를 내리고, 이 때 최소 횟수로 모든 레벨의 점수가 오름차순을 유지하도록 해야 함

 

왜 그리디인지?

- 현재 확인 중인 레벨에서 할 수 있는 최적의 선택은 현재 레벨의 점수가 다음 레벨의 점수보다 1점 작게 하는 것

- 가장 어려운 레벨에서 쉬운 레벨 방향으로 점수를 확인하면서 필요할 때 점수를 깎는 것이 가장 최적의 선택이라고 할 수 있음 - 높은 점수부터 확인하며 점수를 조정할 경우 이전 레벨에 대해 다시 확인할 필요가 없으므로 현재 선택이 이후 선택에 영향을 주지 않음(독립적)

 

2) 아이디어 흐름

① 오름차순 정답지를 만들어두고 주어진 리스트와 차이 계산

제일 먼저 떠올린 방법은 주어진 숫자 리스트의 맨 뒤 원소가 가장 크다고 정해두고 해당 값으로 끝나는 오름차순 리스트를 정답 리스트로 사용하는 것이다. 이게 무슨 말인가 하면..!

 

입력 리스트 [5, 3, 7, 5] (입출력 예시 2)

정답 리스트 [2, 3, 4, 5] (내가 생각한 방식에서 정답지로 쓰고자 하는 리스트)

 

꽤나 그럴 듯한 방법처럼 보이기도 하고 두 개의 예시에서 나와야 하는 값을 잘 출력하기도 해서 제출했더니 결과는 오답이었다.

 

반례를 고민하다가 이 방식으로 처리하지 못하는 경우를 하나 발견했다.

 

입력 리스트 [3, 3, 7, 6]

정답 출력 5 → [2, 3, 4, 5]가 만들어지도록 해야 함

실제 출력 3 → [3, 4, 5, 6]을 정답 리스트로 사용

 

위의 2번 인덱스처럼 정답 리스트에서 각 인덱스에 있어야 하는 값보다 작은 값이 할당된 경우, 값을 올릴 수는 없기 때문에 제대로 된 답을 구할 수 없다.

 

# 첫 번째 오답 코드

import sys

input = sys.stdin.readline

N = int(input())

score = []

for _ in range(N):
    score.append(int(input()))

ascending = [score[-1]-i for i in range(N)]

answer = 0

for real, want in zip(score, sorted(ascending)):
    answer += abs(real-want)

print(answer)

 

 

② 내림차순으로 접근하기

오름차순 방식으로 풀어보려고 계속 고민했는데 이전 값을 신경 써야 하는 상황이 자꾸 생기길래 너무 복잡해서 일단 뒤집어서 생각해보기로 했다. 입출력 예시 2에서 [5, 7, 3, 5] 리스트로 접근하는 방식이다.

 

핵심 로직은 1) i+1번째 요소가 i번째 요소보다 크거나 같으면 2) i+1번째 요소의 값을 (i번째 요소의 값)-1로 갱신하고, 3) 횟수를 기록하기 위한 변수에 (i번째 요소의 값)-1만큼을 더해주는 것이다.

 

그런데 입출력 예제 2는 잘 출력됐지만 입출력 예제 1이 이상하게 출력돼서 다시 확인해보니 answer 값에 score[i]-1 값을 바로 더하는 게 문제였다. [5, 7, 3, 5] 리스트로 확인해보면 7이 5보다 크기 때문에 감소가 이뤄지고 7에서 4로 감소한 만큼 3이 더해져야 하는데 4를 더해주고 있는 것이다.

 

입출력 예제 2가 통과한 게 어쩌면 얻어 걸린 통과일수도 있겠다 싶어 저 부분을 수정하기로 했다.

 

# 두 번째 오답 코드

import sys

input = sys.stdin.readline

N = int(input())

score = []

for _ in range(N):
    score.append(int(input()))

answer = 0

score = score[::-1]

for i in range(0, len(score)-1):
    if score[i+1] >= score[i]:
        new_value = score[i]-1
        
        answer += new_value
        
        score[i+1] = new_value

print(answer)

 

3) 구현

import sys

input = sys.stdin.readline

N = int(input())

score = []

for _ in range(N):
    score.append(int(input()))

answer = 0

score = score[::-1]

for i in range(0, len(score)-1):
    if score[i+1] >= score[i]:
        new_value = score[i]-1
        
        answer += score[i+1]-score[i]+1
        
        score[i+1] = new_value

print(answer)

 

다른 부분은 두 번째 오답 코드와 모두 동일하고 answer 변수에 더해지는 값만 수정해주니까 통과할 수 있었다.

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 뒤에서부터 처리하는 걸 한 번에 떠올리는 것
• 오름차순으로 처리하려고 하니까 현재 값보다 더 작은 값이 이전에 나왔는지를 신경 써야 했고 코드가 너무 복잡해질 것 같았다. 역순으로 확인하는 이유를 알고 쓴 게 아니라 소 뒷걸음질 하다 쥐 잡은 격의 풀이 느낌?

❗ 배운 점

• 현재의 선택이 이후 선택 과정에 영향을 미치지 않는 것도 그리디 알고리즘을 적용할 수 있는 조건에 해당한다. 근데 이건 문제를 보고 한 번에 파악하기는 조금 쉽지 않을수도 있을 것 같다는 생각이 든다.