2847번: 게임을 만든 동준이

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


$O(n)$

큰 레벨부터 보면서 그보다 작은 레벨에서 얻을 수 있는 점수가 해당 레벨에서 얻을 수 있는 점수보다 작게 만든다.

#include<cstdio>
int n, a[100], r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = n - 1; i; i--) if (a[i - 1] >= a[i]) r += a[i - 1] - a[i] + 1, a[i - 1] = a[i] - 1;
    printf("%d", r);
    return 0;
}