백준 28324 <스케이트 연습> Python

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

---

그리디 알고리즘 문제입니다.

 

순서대로 진행할 때 '올리는 건 제한이 없지만 내릴 때는 1씩 밖에 못내린다 / 시작과 마지막은 0 이어야 한다' 라는 사실상 올릴 수 있는 한계가 동적이라는 말을 하고 있습니다.

 

그렇다면 반대로 진행해보겠습니다.

'올릴 때는 1씩 밖에 못올리지만 내리는 건 제한이 없다 / 시작과 마지막은 0 이어야 한다' 로 조건이 바뀌면 상당히 편해집니다. 시작은 0 으로 시작하면 되고, 마지막은 그냥 마지막 속도를 전부 빼주면 됩니다.

 

그냥 최대 제한에 맞춰 1씩 더해주고 제한만큼 내려주고를 반복해주면 풀 수 있습니다.

---

import sys

input = sys.stdin.readline


def solution(N, limits):
    # limits 반전
    limits = list(reversed(limits))
    # 속도 총 합
    v_sum = 0
    # 현재 속도
    now_v = 0
    # 순회
    for limit in limits:
        # 현재 속도 + 1 이 제한 이하면 
        if now_v + 1 <= limit:
            # 올리기
            now_v += 1
        
        # 제한 초과면
        else:
            # 한계치까지 내림
            now_v = limit

        # 속도 합
        v_sum += now_v
    
    print(v_sum)


# 입력
N = int(input().strip())
limits = list(map(int, input().strip().split()))

solution(N, limits)