백준 2847번
https://www.acmicpc.net/problem/2847

문제

후기

⏰ 풀이시간 30분 ++⏰

가장 큰 수는 감소시킬 필요가 없으니, 가장 큰 수 다음으로 큰 수를 감소시키고,

또 그 다음으로 큰 수를 감소시키는 알고리즘을 적용하면 쉽게 풀리는 문제다.

단지 그것을 구현하는 과정에서 은근히 시간이 오래 걸렸다.

i번째 수보다 i+1 번째 수가 더 크다면, 서로 빼는 과정에서 음수가 나올 수 있으므로,

절대값 처리를 해주는 부분만 신경쓰면 되는 문제였다.

나의 풀이

import sys

input = sys.stdin.readline

n= int(input())


li= ([ int(input()) for _ in range(n)])  #점수를 리스트로 받는다. 


li.reverse() #가장 높은 점수가 맨앞으로 올 수 있게 한다. 

result =0  # i+1번째와 i번째가 점수가 증가하는 식으로 되려면 얼마를 증가시켜야 하는가 

ans = 0 #최종으로 몇번 감소했는가 

for i in range(n-1):  # 마지막에서 2번 째 수부터 감소시키면 되니 n번이 아닌 n-1번 

    if li[i+1] > li[i]:  # i+1번째 수가 i보다 크다면 

        result += abs(li[i+1] - li[i] +1)  # 음수가 나올 수 도 있기 때문에 절대값을 취한다. 

        li[i+1] = li[i+1] - result  # 감소시킨 값을 적용해야 한다. 

        ans += result  #최종 결과값에 더해준다. 

        result = 0 #다시 반복해야 되니 초기화 
    
    elif li[i+1] == li[i]:  #값이 같으면 

        result +=1 # 1번만 증가시키면 된다. 

        li[i+1] = li[i+1] - result
        
        ans += result

        result = 0        
    
    else:

        result = 0
    

print(ans)