[백준] 2847 게임을 만든 동준이 (Python 파이썬)

www.acmicpc.net/problem/2847

2847번: 게임을 만든 동준이

문제 설명

첫째 줄에 레벨의 수 N이 주어지고, 다음 줄부터 N+1줄까지 게임 레벨의 난이도가 주어진다.

이전 게임의 레벨은 반드시 다음 게임의 레벨보다 낮아야 하는데, 입력의 상태는 이전 게임이 다음 게임보다 레벨이 높은 경우가 존재한다.

최소한의 횟수로 레벨을 오름차순으로 나타내어야 하며, 레벨 1감소가 1회이다.

---

풀이 과정

현재 게임이 다음 게임보다 레벨이 낮게 하려면 어떻게 해야할까?

다음 게임의 레벨보다 낮게 설정하면 된다. 단, 최소한의 횟수를 사용하라고 했으므로 다음 게임보다 1만큼 적게 설정해주면 된다.

 

여기서 주의해야 할 점은, 뒷 게임부터 낮춰주어야 한다는 것이다.

앞에서 부터 낮추게 되면, 다시 앞의 난이도가 뒤의 난이도보다 높아지는 경우가 발생하기 때문이다.

예를 들어 보자.

5 9 4 8 -> 4 9 4 8 -> 4 3 4 8 -> 4 3 7 8

이렇게 되면, 앞의 난이도를 줄였음에도 불구하고 뒤의 난이도가 더 작아지는 상황이 발생한다.

따라서, 뒤의 난이도부터 수정을 해주어야 이런 상황이 발생하지 않는다.

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

count = 0
for i in range(n-2, -1, -1):
    if score[i] >= score[i+1]:
        count += score[i] - score[i+1] + 1
        score[i] = score[i+1]-1

print(count)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !