게임을 만든 동준이

코드

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <sstream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N,ans=0;
    cin >> N;
    vector<int> v(N);
    for(int i=0;i<N;i++) cin >> v[i];
    for(int i=N-1;i>0;i--)
    {
        int cur = v[i];
        int prev = v[i-1];
        if(cur <= prev)
        {
            v[i-1] = cur-1;
            ans += prev-cur+1;
        }
    }
    cout << ans;
    return 0;
}

• 원리
  : 뒤에 최상위 레벨부터 내려오면서 최소한 차이가 나도록 감소
• 주의할 점
  : 처음에 하위 레벨부터 맞추다보니 내가 맞춘 앞 레벨보다 다음 수가 더 작아지는 경우가 생김
  ex) 10 5 4 9 일 때
  1) 앞에서부터 맞추면 4 3 4 9 가 된다.- 오답
  2) 뒤에서부터 하면 2 3 4 9 가 된다 - 정답