99클럽 코테 스터디 16일차 TIL + 그리디

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

import sys
input = sys.stdin.readline

n = int(input())
levels = []
answer = 0

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

for i in range(n-1,0,-1): #뒤에서부터 난이도 조절
    if levels[i] <= levels[i-1]:
        answer += (levels[i-1] - levels[i] + 1) # 뒷난이도와 앞난이도 차이가 1이 나도록 수정 ex. 7, 5 > 7이 4가 되어야 한다. > 7-5+1
        levels[i-1] = levels[i] - 1

print(answer)

• 처음에 문제를 이해하기 어려웠다. 동준이는 레벨을 난이도 순으로 배치했고 어려운 난이도의 점수가 쉬운 난이도의 점수보다 높아야한다. 이때, 최소한으로 변경하는 방법을 구해야한다.
  • 그러므로 이전 난이도의 점수가 이후 난이도의 점수보다 1 낮아야 한다.
  • 5 3 7 5 >> 2 3 4 5 즉, 5가 2 7,4가 되어야 하므로 총 6번 감소시킨다.
• 뒤에서부터 점수를 비교해야 점수가 또다시 수정될 일이 없다.
• for문의 idx를 낮아지게 한 경우 헷갈릴 수 있다.
  • 위 for문의 idx는 n-1, n-2 .... 1까지 비교를 한다.
• 두번째 방법으로, reverse() 함수를 이용해 levels를 뒤집어 내림차순으로 생각할 수 있다.
  • 5 3 7 5 >> 5 7 3 5 로 뒤집어지므로 for문을 idx 1부터 n까지 비교할 수 있다.
  • 이때는 앞 idx의 점수가 뒤 idx의 점수보다 1이 커야한다.
  • 5 7 3 5 >> 5 4 3 2 가 되어야 하므로 똑같이 7이 4, 5가 2가 되어야 하므로 6번의 감소를 하면된다.