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

문제

서기 2XXX년, 지구가 소행성과 충돌할 위기에 처했다! 똑똑한 과학자 키파는 평행 우주를 누비며 지구를 대신할 행성을 찾는 막중한 임무를 맡게 되었다.

우리는 현재 지구(=행성 0)에 있다. 여러 요인을 고려한 결과, 행성 1, 행성 2, …, 행성 (n-1)을 순서대로 확인하고 지구(=행성 n)에 돌아오는 것이 비용상 최적임을 알아냈다. 모든 정수 1 ≤ i < n에 대해, 행성 i은 지구가 아니다.

지구에는 "초고속 걷기 기계"라는, 속도를 원하는 만큼 올릴 수 있는 특수한 장치가 있다. 지구를 벗어나면 속도를 떨어뜨릴 수 있을 뿐 높일 수는 없다.

다음 지역에 가기 위해서는 원칙적으로는 필요한 속도를 정확히 맞춰야 하지만, 다행히도 평행 우주는 일정한 간격을 두고 있기 때문에 필요한 속도의 양의 정수 배로도 다음 지역으로 이동할 수 있다. 또한, 충분히 빠른 속도로 이동 중이며, 지구의 대체 행성으로 적합한지 아닌지는 도착한 뒤 바로 알 수 있기 때문에 어떤 행성에서는 도달한 뒤 속도를 유지한 채 다음 행성으로 이동할 수도 있다.

모든 1 ≤ i ≤ n에 대해, 행성 (i-1)에서 행성 i로 이동하는 데 필요한 (최소) 속도 vi가 주어진다. 지구에서 올려야 하는 속도를 최소화하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 3·105)이 주어진다.

둘째 줄에 n개의 정수 v1, v2, …, vn이 공백을 사이에 두고 주어진다. 모든 정수 1 ≤ i ≤ n에 대해 1 ≤ vi ≤ 109을 만족한다.

출력

수 하나를 출력한다. 이 수는 지구에서 올려야 하는 속도의 최솟값이다.

예제 입출력

• 예제 입력 1

5
300 400 500 400 300

• 예제 출력 1

900

Solution

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long answer = 0;
    int N;
    cin >> N;
    vector<long long> vec(N);
    for(int i = 0; i < N; i++) cin >> vec[i];
    for(int i = N - 1; i >= 0; i--){
        if(answer <= vec[i]) answer = vec[i];
        else{
            if(answer % vec[i]){
                answer = (answer / vec[i] + 1) * vec[i];
            }
        }
    }
    cout << answer << '\n';
}

역으로 계산을 해 보아야 한다. 정방향으로는 계산하기 힘든 문제.
어느 시점에서 몇배속을 해야하는가? 에 대해 결정해야 하는 문제다. 특정 시점에서 요구하는 속도가 늘어나는 시점이 있다. 이 시점에서 얼마나 늘려야 하는가를 구하는 문제다.

역으로 체크하면서 그 시점에서 요구하는 속도 만큼 계속 진행해도 상관없는지를 확인해본다. 그런데 언젠가 그게 아닌 시점이 온다. 속도가 줄어드는(역으로 생각하면 속도를 올려야 하는 시점) 시점에서 현재까지 갱신되고있던 속도 / 그 시점에서의 속도 + 1 를 해준다. 몇 배속을 해야하는 지 확인해야하니까. 그리고 해당 시점에서의 속도를 곱해준다. 그러면 모든 시점에서 만족하는 속도가 계속해서 갱신된다.