백준 2847번 파이썬 문제풀이(게임을 만든 동준이)

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

2847번: 게임을 만든 동준이

 

---

처음에 전체를 N번 동안 돌고 각 반복문마다 앞에서 앞,뒤(i,i+1) 값을 보면서 앞의 값이 뒤의값보다 크다면 앞의 값을 (앞의값 - 뒤의 값 + 1)으로 바꿔주는 방식으로 생각했다.

다행이 N = 100이라 O(N^2)이 통과되었지만 N 이 10000이상일때도 해당 문제를 풀려면 O(N)방식을 생각해야한다. 따라서 그 방식이 뒤에서부터 값을 비교하며 만약 앞에값이 뒤값보다 더 크다면 해당 값을 앞의값 - 뒤의 값 + 1 로 바꿔주는 고 그 값을 계속 정답변수에 더해주는 방식이다. 

N = int(input())

arr = [int(input()) for _ in range(N)]

cnt = 0

for i in range(1, N)[::-1]:

    if arr[i - 1] >= arr[i]:
        cnt += (arr[i - 1] - arr[i] + 1)
        arr[i - 1] -= (arr[i - 1] - arr[i] + 1)

print(cnt)