[BOJ 2847, Python 3] 게임을 만든 동준이

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

2847번: 게임을 만든 동준이

 

풀이

arr[i] < arr[i+1]만 만족하면 되는데, →방향으로 2중 for문을 돌리거나 ←방향으로 for문을 돌리는 풀이가 존재합니다.

 

1. →방향으로 2중 for문

arr[i] >= arr[i+1]일 때 arr[i]는 arr[i+1] - 1이 되는 것이 가장 최소로 점수를 내릴 수 있는 방법입니다.

2중 for문을 하는 이유는 [5, 5, 3]이 입력 값으로 들어올 때 단순 for문으로만 하면 arr배열의 값이  [4, 2, 3]으로 변경될 것이다. N = 100이므로 O(N^2)가 돌아가니 2중 for문을 하여 [5, 5, 3] -> [4, 2, 3] -> [1, 2, 3]로 바꾸어주면 됩니다.

 

 

2. ←방향으로 for문

arr[i] <= arr[i-1]일 때 1번 방법의 for문과 같습니다. 이건 왜 한 번만 해도 되냐면 1번 방법으로는 for문 1겹으로만 하면 arr[i] > arr[i-1]이 보장이 되지 못하는데, ←방향으로 for문을 한 번 돌리면 arr[i] > arr[i-1]이 보장되기 때문입니다.

 

 

 

코드

풀이1

n = int(input())
arr = [int(input()) for i in range(n)]
ans = 0
for i in range(n):
    for j in range(n-1):
        if arr[j] >= arr[j+1]:
            ans += arr[j] - (arr[j+1] - 1)
            arr[j] = arr[j+1] - 1
print(ans)

풀이2

n = int(input())
arr = [int(input()) for i in range(n)]
ans = 0
for i in range(n - 1, 0, -1):
    if arr[i] <= arr[i-1]:
        ans += arr[i-1] - (arr[i] - 1)
        arr[i-1] = arr[i] - 1
print(ans)