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

1. 문제 📚

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

2847번: 게임을 만든 동준이

2. 입출력 예 📋

3. 알고리즘 ✅

점수를 내리는 것을 최소한으로 하는 방법은 뒤에 숫자가 1이 더 크면 된다 → 그리디

나는 while 문을 돌려가며 하나씩 -1을 해주고 마지막에 리스트를 전부 순회하며 뒤에 숫자가 큰 지 다시 체크를 해주었다.

맞긴했지만, 더 좋은 방법이 있을 것같아 구글링해보았다!



다른 사람들 코드를 보니 뒤에부터 리스트를 순회하며 뒤의 값보다 1만큼 작게 만들어주었다 

앞으론 뒤에서 부터 하는 생각도 해봐야겠당 😅

4. 내 코드 💻

import sys
input = sys.stdin.readline

N = int(input().strip())

scores = [int(input().strip()) for _ in range(N)]

index = 0
answer = 0
last_check = False

while True:
    if last_check:
        break

    if scores[index] >= scores[index + 1]:
        scores[index] -= 1
        answer += 1
    else:
        index += 1
	
    # 뒤의 값이 더 큰지 체크 아니라면 다시 처음부터 -1 해주기
    if index == len(scores) - 1:
        for i in range(N - 1):
            if scores[i] >= scores[i + 1]:
                index = 0
                last_check = False
                break
            else:
                last_check = True

print(answer)

5. 다른 사람 코드 💻

import sys
input = sys.stdin.readline

N = int(input().strip())

scores = [int(input().strip()) for _ in range(N)]

answer = 0

for i in range(N - 1, 0, -1):
    if scores[i] <= scores[i - 1]:
        answer += (scores[i - 1] - scores[i] + 1)
        scores[i - 1] = scores[i] - 1

print(answer)