문제

여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, $N$개의 중간 지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 $0$의 속력으로 출발하여, $1$번 중간 지점부터 $N$번 중간 지점까지 번호가 증가하는 순서대로 방문하고, $0$의 속력으로 도착 지점에 도달한 이후 종료된다.

각 중간 지점에는 속력 제한 $V_i$가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 $1$만큼만 낮출 수 있다. 단, 출발 지점과 도착 지점을 제외한 위치에서 속력은 $0$이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다.

연습의 성과는 각 지점에서의 속력의 합과 같으므로 여러분은 이를 최대화하려고 한다. 스케이트 코스의 속력 제한이 주어졌을 때, 그 코스에서 얻을 수 있는 최대 연습의 성과를 구해보자.

예를 들어, 중간 지점이 $3$개인 코스의 속력 제한이 $V=[2, 3, 1]$로 주어진 경우, $2$번 중간 지점에서 $3$의 속력을 유지한다면 $3$번 중간 지점에서 $1$이하의 속력이 되도록 조절하는 것이 불가능하다. 이 코스에서 가능한 연습 방법 중 하나로, $[2, 2, 1]$의 순서대로 속력을 조절한다면 속력의 합은 $2 + 2 + 1$인 $5$가 된다. 다른 가능한 연습 방법으로 $1, 1, 1$과 $1, 2, 1$이 있지만, 이들의 속력의 합은 $5$를 초과하지 않는다. 따라서 이 코스에서 얻을 수 있는 가장 큰 연습의 성과는 $5$이다.

정답

#include <iostream>
#include <vector>

#define ll long long

using namespace std;
int main(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int n; cin >> n;
  vector<ll> v(n,0);
  for (int i=0;i<n;i++) cin >> v[i];
  ll temp = 0;
  ll sum = temp;
  for (int i=v.size()-1; i>=0; i--) {
    if (temp < v[i]){
      temp++;
      sum += temp;
    }else {
      temp = v[i];
      sum += v[i];
    }
  }
  cout << sum;
  return 0;
}

풀이

이 문제의 포인트는 뒤에서 앞으로 속력을 구하는 것이다. 속력을 올리는 것은 제한이 없이만 속력을 줄이는 것은 1만큼 줄일 수 있기 때문이다. 예시로 $23, 7, 1, 5$ 이라는 숫자가 들어왔다고 가정하자. 뒤집어서 뒤에서 부터 생각하면 $5, 1, 7, 23$, 하지만 처음과 끝은 항상 속력이 0이므로 $0, 5, 1, 7, 23$ 이라고 생각해야 한다. $0$부터 시작해서 다음에 만나는 $5$까지, 속력은 $1$만큼만 줄일 수 밖에 없기 때문에 속도는 $1$, 똑같이 다음으로 넘어가서 숫자는 $1$, 속도가 동일하기 때문에 $1$을 유지한다. 다음은 $7$, 속력은 1만큼 줄일 수 있기 때문에 기존 속도에서 $1$을 더해준 $2$, 마지막으로 $23$도 똑같이 속력을 $1$만큼 줄일 수 있기 때문에 속력 $3$으로 정답은 $7$이 된다.

따라서, 정답은 $3, 2, 1, 1$이 된다.