[Python] 백준/BOJ - 2847번: 게임을 만든 동준이

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

2847번: 게임을 만든 동준이

 

문제

동준이가 만든 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 동준이는 레벨을 난이도 순으로 배치했는데, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게 각 레벨을 클리어할 때 주는 점수가 증가하게 만드려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수여야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어지고, 정답이 여러가지인 경우 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

 

입력

첫째 줄: 레벨의 수 N ( 1 <= N <= 100 )

다음 N개 줄: 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. ( 1 <= 점수 <= 20000 )

 

출력

점수를 몇 번 감소시키면 되는지 출력

 

예제 입력 1

3
5
5
5

 

예제 출력 1

3

 

풀이

그리디로 풀면 될 것 같다는 생각을 하고, 최대한 그리디스럽게 생각해보자 하며 문제를 풀어보았다.

막연하게 생각해보면 처음 레벨부터 확인하면서 다음레벨보다 크거나 같다면 다음레벨보다 1점이 작도록 만들어주면 된다. 하지만 다음레벨이 그 다음레벨보다 크거나 같은 경우 다음레벨이 줄어들기 때문에 처음 레벨도 다시 수정해줘야 하는 경우가 발생한다. 이를 대비해서 맨 마지막 레벨부터 먼저 확인해주면 불필요한 반복을 없애줄 수 있다.

 

n = int(input())
scores = []
cnt = 0

for _ in range(n):
    scores.append(int(input()))

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

print(cnt)

 

n-1번째(맨 뒤 요소) 부터 0까지 1씩 감소시키며 for문을 돌아준다. 현재 요소보다 그 전의 요소가 크거나 같을 경우(점수를 감소시켜줘야 하는 경우) 점수의 차이(scores[i-1] - scores[i])에 1을 더한 결과를 cnt에 더해준다.

예를 들어 점수가 [6, 5]일 경우 6을 4로 만들어줘야 하기 때문에 감소시켜줘야 하는 점수 cnt는 scores[0] - scores[1] + 1이고, scores[0]은 scores[1] - 1값으로 바꿔줘야 한다.

 

---

 

처음 풀 때는 for문을 0부터 돌고 n에서 i를 빼주는 방식으로 했었는데 파이썬 range의 파라미터가 range([start,] stop [,step])이라는 것을 잊고 있었다. 위의 코드처럼 작성해주면 n-1부터 0까지 -1씩 증가하는 for문이 된다. 좀 더 파이썬스럽게 생각할 수 있도록 해야겠다.