파이썬) 게임을 만든 동준이 - BOJ

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

2847번: 게임을 만든 동준이

 

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

cnt = 0

for i in range(n-1, 0, -1):
    if arr[i] <= arr[i-1]:
        # 현재보다 현재 - 1 값이 같거나 크다면
        while arr[i] <= arr[i-1]:
            # 현재값이 더 클때까지
            cnt += 1
            arr[i-1] = arr[i-1] - 1

print(cnt)

 

문제를 쭉 풀어보다가 내가 그리디 문제를 공통적으로 약하다는 생각이 문득 들었다.

때문에 앞으로 몇 번은 그리디를 집중적으로 풀어볼까 한다.

 

각설하고 이 문제를 설명하자면, 이 문제는 배열의 마지막 인덱스부터 시작해야한다.

문제 조건이 앞에 점수보다 뒤에 나오는 점수가 더 크기 때문에

최적의 해란 배열의 마지막번째를 가장 큰 값으로 생각한 뒤, 점차 낮은 레벨의 점수들을 -1씩 깎아내리는 것이다.