백준 - 2847: 게임을 만든 동준이 - Greedy

https://www.acmicpc.net/problem/2847

2847번: 게임을 만든 동준이

뒤에서 부터 보면서 만약 다음 수가 현재 수보다 크다면, 현재 수보다 1 작은 값으로 만들어주면 됩니다.

1 작은 값으로 만들어야 점수를 낮추는 횟수를 최소화 할 수 있습니다.

 

문제 조건에서 항상 답이 존재하는 경우만 주어지기 때문에 1보다 작아지는 경우는 생각하지 않아도 됩니다.

 

from sys import stdin
input = stdin.readline

n = int(input())

score = []
for _ in range(n):
    score.append(int(input()))

current = score[-1]
sum_of_decreased_score = 0
for ii in range(n-2, -1, -1):
    if score[ii] >= current:
        sum_of_decreased_score += score[ii] - (current -1)
        score[ii] = current -1
    current = score[ii]

print(sum_of_decreased_score)