[그리디 알고리즘] 2847번 게임을 만든 동준이 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/2847

2847번: 게임을 만든 동준이

아래 작성된 답안은 제가 직접 작성 후 백준 페이지에서 채점하여 정답으로 인정된 답안입니다.
공식 답안이 아니므로 최적의 해가 아닐 수 있으며, 답안은 다른 분들과 상이할 수 있습니다.

 

[풀이]

n = int(input())
point = [int(input()) for i in range(n)]
point.reverse()
count = 0
for i in range(len(point)-1):
    if point[i+1] >= point[i]:
        count += (point[i+1]-point[i]+1)
        point[i+1]=point[i]-1
print(count)

이 문제의 핵심은 가장 마지막에 입력받은 숫자를 최대값으로 잡고, n번째 값과 n-1번째 값을 비교하여 n-1번째 값이 n보다 1작은 수로 만들어주는 것입니다.

이를 위해 point 리스트에 작성된 단계별 점수를 reverse를 활용하여 뒤집었습니다.

이후 for 문을 활용하여 i+1번째 값이 i번째 값보다 크면(낮은 레벨의 점수가 높은 레벨의 점수보다 높다는 뜻. 줄여줘야함) 두 값의 차이+1만큼 count에 더해준 후 point[i+1]번째 값을 point[i] 번째 값보다 1만큼 작은 수로 변경해주었습니다.

 

감사합니다.