[Baekjoon][Python] 2847번 게임을 만든 동준이

2847번 게임을 만든 동준이

문제

풀이

문제의 조건을 잘 살펴보고 풀면 된다.
1. 레벨을 클리어할 때 주는 점수가 증가해야 한다.
2. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번
3. 항상 답이 존재하는 경우만 주어진다.
4. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법

생각한 알고리즘은
가장 마지막 값부터 처음 값으로 비교하면서, 해당 값이 이전 값보다 크거나 같다면 그 차이 + 1 만큼 감소시키고 차이 + 1을 감소 횟수에 더하는 것이다. 4번 조건에 의해 차이 + 1 만큼만 감소시키는 것이다. 따라서 최적해를 보장하게 된다.

입력이

3
5
5
5

이렇게 들어오면, 마지막 값이 5부터 앞으로 가면서 비교를 하게 된다.
3번째 5와 2번 째 값인 5를 비교해서 그 차이인 0 + 1 만큼 2번 째 5에 빼주면 된다.
그러면 5 4 5 가 되고, 다음으로 2번 째 값 4와 다음 1번째 값 5의 차이 1 + 1을 빼주면 5 4 3 이 되므로, 총 감소 횟수는 3이 된다.

이를 구현한 코드는 다음과 같다.

import sys
N = int(sys.stdin.readline())
score = []

for i in range(N):
    score.append(int(sys.stdin.readline()))

count = 0
for i in range(N - 2, -1, -1):
    if score[i + 1] <= score[i]:
        diff = score[i] - score[i + 1] + 1
        count += diff
        score[i] = score[i] - diff
    else:
        score[i] = score[i]

print(count)

결론

완전히 쉬운 문제는 아니었지만, 아이디어가 생각이 나니 쉽게 풀렸다. 그리디 문제였는데, 그리디 문제는 아이디어를 생각해내는 것이 가장 어려운 것 같다. 꾸준히 연습하자.