[C++][백준 31964] 반품 회수

문제

접근 방법

1부터 N까지 순서대로 직선 위에 있다 할 때 N개의 반품을 회수하려면 결국 N번째 반품을 회수해야 합니다.
N번째 반품을 회수하면 그다음에는 N-1번째 반품을 회수해야 합니다.

모든 반품은 이미 회수할 수 있는 시간이라면 그대로 지나갈 것이고 대기해야 한다면 대기하고 회수하면 됩니다.

가장 우측에 존재하는 것은 무조건 도달해야 얻을 수 있다는 점을 고려해야 합니다.

코드

#include <iostream>
#include <vector>
using namespace std;
using pii = pair<int, int>;
int N, answer, curX;
vector<pii> XT;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N;
    XT = vector<pii>(N);
    for (pii &p : XT)
    {
        cin >> p.first;
    }
    for (pii &p : XT)
    {
        cin >> p.second;
    }

    for (int i = N - 1; i >= 0; --i)
    {
        const pii &p = XT[i];
        int diff = max(abs(p.first - curX), p.second - answer);
        answer += diff;

        curX = p.first;
    }

    cout << answer + curX;
    return 0;
}

풀이

남아 있는 반품 중 가장 우측에 존재하는 건 결국 도달해야 얻을 수 있습니다.
이는 가장 우측에 존재하던 반품이 사라져도 동일합니다.
즉 가장 우측에 있는 것부터 차례대로 기다렸다가 회수하면 되는 것입니다.