[Python] 2847번 게임을 만든 동준이

✏️ 문제

 

문제 파악

마지막에 오는 점수가 제일 큰 점수가 되어야 하므로 배열을 끝에서부터 훑으며 마지막 점수를 기준으로 앞에 있는 점수들을 바로 뒤에 있는 점수보다 1점 더 작은 점수로 감소하는 방향으로 코드를 짰다.

 

알고리즘

• 그리디 알고리즘

 

 

코드

n = int(input())
de = 0
score = []

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

for i in range(n-1, 0, -1): # 뒤에서부터 읽어오기
  if score[i-1] - score[i] > 0:    # 크면 바로 뒤에 있는 점수보다 1점 작은 점수가 되도록 조정
    de += (score[i-1] - score[i] + 1)
    score[i-1] = score[i] - 1
  elif score[i-1] - score[i] == 0: # 같으면 1점만 차이를 둠
    de += 1
    score[i-1] = score[i] - 1

print(de)