백준 2847 게임을 만든 동준이 Python

🐸 문제 정보

2847번: 게임을 만든 동준이

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

06.12m

 

📝 풀이

아주 간단한 그리디 문제였다. 풀이 순서는 아래와 같다.

1. 점수를 뒤에서부터 순회한다.
2. 현재 요소가 직전 요소보다 크거나 같다면, 직전 요소보다 1 작은 수를 대입한다.
   • 이 때 현재 요소의 원래 값과 직전 요소보다 1 작은 수의 차이가 점수를 감소시키는 횟수이며, 이것의 총합이 답이다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
scores = [int(input().rstrip()) for _ in range(n)]
res = 0

for i in range(n - 2, -1, -1):
    if scores[i] >= scores[i + 1]:
        temp = scores[i + 1] - 1
        res += (scores[i] - temp)
        scores[i] = temp

print(res)