[백준 2847번] 게임을 만든 동준이 - 파이썬

문제 링크:

 

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

2847번: 게임을 만든 동준이

 

---

풀이 과정:

 

이 문제는 사고의 전환이 필요한 그리디 문제이다. 

맨 처음 레벨부터 점수를 감소시키는 것이 아닌, 맨 마지막 레벨부터 점수를 감소시켜야 한다.

그 이유는 쉬운 레벨을 클리어할 때 점수  < 어려운 레벨을 클리어할 때 점수를 부여하기 때문이다.

 

일반적으로 우리가 사용하는 for 구문에 사용되는 range(start, end, step) 함수에서 start보다 end가 큰 값을 넣는 경우가 많다.

하지만 이 문제는 역으로, start가 end보다 큰 형태로 반복문을 실행하여 결과를 출력해보자.

 

풀이 코드:

 

# 2847번 게임을 만든 동준이

n = int(input())

# 변수 생성
level_score = []
count = 0

# 레벨 점수 리스트 받아오기
for _ in range(n):
  level_score.append(int(input()))

# 마지막 레벨부터 처음 레벨까지 1개씩 가져오며
for i in range(n-1, 0, -1):
  # 현재 레벨이 전 레벨보다 점수가 작거나 같다면
  if level_score[i] <= level_score[i-1]:
    # 점수를 (레벨 차이 + 1)만큼 감소
    count += (level_score[i-1] - level_score[i]) + 1
    # 전 레벨은 현재 레벨보다 1 작은 점수 부여
    level_score[i-1] = level_score[i] - 1

# 정답 출력
print(count)

 

2847번 게임을 만든 동준이