백준 2874번 게임을 만든 동준이 파이썬

문제

입력 , 출력

solution

import sys

input = sys.stdin.readline
n = int(input())
arr = [0 for i in range(n)]
for i in range(n):
    arr[i] = int(input())
arr.reverse()
cnt = 0
for i in range(1, n):
    if arr[i] >= arr[i - 1]:
        cnt += arr[i] - (arr[i - 1] - 1)
        arr[i] = arr[i - 1] - 1
print(cnt)

설명

배열을 거꾸로 뒤집어서 i번째 인덱스값이 i-1보다 클 경우에는
i번째 값 -1을 만들면 최소한으로 감소하게 할수있으므로 결과값 cnt에는
arr[i] - (arr[i-1]-1) 만큼 i번째 값을 감소시키면 되므로 이 값을 저장한다.
그리고 arr[i] 를 arr[i-1]-1 값을 저장한다.

후기

그리디는 여전히 어렵다

좋은 웹페이지 즐겨찾기