[그리디/Greedy] 백준 2847 게임을 만든 동준이 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2847번: 게임을 만든 동준이

 

 

 

2. 문제 풀이

 레벨에 따라 오름차순으로 경험지를 설정해야 합니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 가장 높은 레벨부터 거꾸로 거슬러 올라가면서, 이전 레벨보다 경험지가 많으면 깎습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
level = []
for _ in range(n):
    level.append(int(input()))

# 그리디 알고리즘
cnt = 0  # 레벨을 감소시키는 횟수
post = level[-1] + 1  # 차후 레벨의 경험지
for i in level[::-1]:
    # 차후 레벨보다 경험지가 높다면 낮춤
    if post <= i:
        cnt += i - post + 1
        post -= 1

    # 차후 레벨보다 경험지가 낮다면 넘어감
    else:
        post = i
print(cnt)