28324. 스케이트 연습

---

문제

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

28324번: 스케이트 연습

---

분석

입력 요구 사항:

1. N - 1<=N<=500,000(5E+5), 속력제한의 수

2. Vi - 1<=Vi<=1,000,000,000(1E+9), 각 속력제한의 범위

 

출력 요구 사항:

1. 가장 큰 성과 - 시작과 도착 속력이 0일때, 중간에 얻을 수 있는 속력의 합

---

풀이

드디어 종강(반만 종강임)을 맞이했다.

 

속력을 높일땐 마음대로지만, 낮출 땐 무조건 1씩만 가능해서 처음부터 계산해 나가기엔 값을 뭐로 설정해야 할지도 애매하고 제한을 못 맞추는 일이 생길 거 같았다. 그래서 뒤에서부터 추적하는 방식을 사용했다.

 

N개의 중간지점에서 도착지점의 속도가 0이면 N번째 지점의 최대 속력은 1이 될 것이다.

N-1번째 지점의 최대 속력은 2가 될 것이고,

N-2번째 지점의 최대 속력은 3이 될 것이고,

...

1번째 지점의 최대 속력은 N-1이 될 것이다.

 

대충 단조감소 수열(x>=y, f(x)>=f(y))을 만들면 되는 것 같다.

N번째 지점의 속도가 1이고, N-1번째 지점부턴 속도를 1씩 올려서

제한에 안 걸리면 올린 값으로, 안되면 제한에 맞게 조정을 해주었다. 

 

예를 들어 1 2 3 4 5이면

5번 지점에서 속도는 1, 제한은 5이므로 1의 성과를 얻는다.

4번 지점에서 속도는 2, 제한은 4이므로 2의 성과를 얻는다.

3번 지점에서 속도는 3, 제한은 3이므로 3의 성과를 얻는다.

2번 지점에서 속도는 4, 제한은 2이므로, 속도를 2로 낮춰야 하고, 2의 성과를 얻는다.

1번 지점에서 속도는 3, 제한은 1이므로, 속도를 1로 낮춰야 하고, 1의 성과를 얻는다.

 

1번->5번 지점순으로 보면 [1,2,3,2,1]이 된다.

---

잡담

수열의 역방향 추적은 문제 접근을 쉽게 만들어줄 때도 있다.

#include<iostream>
#include<sstream>
#include<bitset>
#include<set>
#include<unordered_map>
#include<map>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<tuple>
#include<algorithm>
#include<string>
#include<numeric>
#include<functional>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<chrono>

// ---------- 사용자 정의 상수 ----------
#define PI 3.141592653589793
#define THOUSAND 1E+3
#define MILLION 1E+6
#define BILLION 1E+9
#define INF 1E+8
#define EPSILON 1E-9

// ---------- 사용자 정의 자료형 ----------
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

typedef pair<char, char> Pcc;
typedef pair<char, int> Pci;
typedef pair<char, string> PcS;
typedef pair<int, bool> Pib;
typedef pair<int, int> Pii;
typedef pair<int, char> Pic;
typedef pair<int, string> PiS;
typedef pair<double, double> Pdd;
typedef pair<LL, LL> PLL;
typedef pair<string, int> PSi;
typedef pair<string, LL> PSL;
typedef pair<string, string> PSS;

typedef vector<string> Words;

// ---------- 템플릿 자료형 ----------
template<typename T> struct Matrix2D {
    vector<vector<T>> m2;

    Matrix2D() {};
    Matrix2D(const size_t R, const size_t C, const T INIT) {
        m2 = vector<vector<T>>(R, vector<T>(C, INIT));
    }
};
template<typename T> struct Matrix3D {
    vector<vector<vector<T>>> m3;

    Matrix3D() {};
    Matrix3D(const size_t H, const size_t R, const size_t C, const T INIT) {
        m3 = vector<vector<vector<T>>>(H, vector<vector<T>>(R, vector<T>(C, INIT)));
    }
};

// ---------- 템플릿 함수 ----------
template<typename T> vector<T> InitVector(const size_t SIZE, const T INIT) {
    return vector<T>(SIZE, INIT);
}
template<typename T> vector<vector<T>> Init2DVector(const size_t R, const size_t C, const T INIT) {
    return vector<vector<T>>(R, InitVector(C, INIT));
}
template<typename T> vector<vector<vector<T>>> Init3DVector(const size_t H, const size_t R, const size_t C, const T INIT) {
    return vector<vector<vector<T>>>(H, Init2DVector(R, C, INIT));
}

template<typename T1, typename T2> pair<T1, T2> LoadPair() {
    pair<T1, T2> p;
    cin >> p.first >> p.second;
    return p;
};
template<typename T> vector<T> LoadVector(const size_t SIZE) {
    vector<T> V(SIZE);
    for (T& e : V) {
        cin >> e;
    }
    return V;
}
template<typename T1, typename T2> vector<pair<T1, T2>> LoadVector(const size_t SIZE) {
    vector<pair<T1, T2>> V(SIZE);
    for (pair<T1, T2>& p : V) {
        p = LoadPair<T1, T2>();
    }
    return V;
}
template<typename T> vector<vector<T>> Load2DVector(const size_t R, const size_t C) {
    vector<vector<T>> V(R, vector<T>(C));
    for (vector<T>& row : V) {
        row = LoadVector<T>(C);
    }
    return V;
}
template<typename T1, typename T2> vector<vector<pair<T1, T2>>> Load2DVector(const size_t R, const size_t C) {
    vector<vector<pair<T1, T2>>> V(R, vector<pair<T1, T2>>(C));
    for (vector<pair<T1, T2>>& row : V) {
        row = LoadVector<T1, T2>(C);
    }
    return V;
}

template<typename T1, typename T2> void PrintPair(const pair<T1, T2>& p, const string sepsPair) {
    cout << p.first << sepsPair << p.second;
}
template<typename T> void PrintVector(const vector<T>& V, const string sepsC) {
    for (const T& e : V) {
        cout << e << sepsC;
    }
}
template<typename T1, typename T2> void PrintVector(const vector<pair<T1, T2>>& V, const string sepsR, const string sepsPair) {
    for (const pair<T1, T2>& p : V) {
        PrintPair<T1, T2>(p, sepsPair);
        cout << sepsR;
    }
}
template<typename T> void Print2DVector(const vector<vector<T>>& V, const string sepsR, const string sepsC) {
    for (const vector<T>& row : V) {
        PrintVector(row, sepsC);
        cout << sepsR;
    }
}
template<typename T1, typename T2> void Print2DVector(const vector<vector<pair<T1, T2>>>& V, const string sepsR, const string sepsC, const string sepsPair) {
    for (const vector<pair<T1, T2>>& row : V) {
        PrintVector<T1, T2>(row, sepsC, sepsPair);
        cout << sepsR;
    }
}

template<typename T, typename Compare = less<T>> void SortAll(vector<T>& V, Compare cmp = Compare()) {
    sort(V.begin(), V.end(), cmp);
}
template<typename T, typename Compare = less<T>> void SortAll2D(vector<vector<T>>& V, Compare cmp = Compare()) {
    for (vector<T>& row : V) {
        Sort(row, cmp);
    }
}
template<typename T, typename Compare = less<T>> void StableSortAll(vector<T>& V, Compare cmp = Compare()) {
    stable_sort(V.begin(), V.end(), cmp);
}
template<typename T, typename Compare = less<T>> void StableSortAll2D(vector<vector<T>>& V, Compare cmp = Compare()) {
    for (vector<T>& row : V) {
        StableSort(row, cmp);
    }
}

template<typename T> size_t LowerBoundIndex(const vector<T>& V, const T target) {
    const size_t index = lower_bound(V.begin(), V.end(), target) - V.begin();
    return index;
}
template<typename T> size_t UpperBoundIndex(const vector<T>& V, const T target) {
    const size_t index = upper_bound(V.begin(), V.end(), target) - V.begin();
    return index;
}

template<typename Number> vector<Number> InitArithmeticSeq(const size_t N, const Number firstTerm = 1, const Number commonDiff = 1) {
    vector<Number> seq;

    for (size_t i = 0; i < N; i++) {
        seq.push_back(firstTerm + i * commonDiff);
    }

    return seq;
}

// ---------- 열거형 상수 ----------

// ---------- 사용자 정의 함수 및 연산자 ----------
LL CalcMaxResult(const vector<LL>& V, const int N);

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    vector<LL> V;
    LL maxRes;
    int N;

    cin >> N;

    V = LoadVector<LL>(N);
    maxRes = CalcMaxResult(V, N);

    cout << maxRes << "\n";

    return 0;
}

LL CalcMaxResult(const vector<LL>& V, const int N) {
    LL maxRes = 1;
    LL v = 1;

    for (LL i = N - 2; i >= 0; i--) {
        maxRes += (V[i] >= (++v)) ? v : (v = V[i]);
    }

    return maxRes;
};