[C++][백준 17451] 평행 우주

문제

접근 방법

문제가 조금 이해하기 어렵게 작성됐습니다.

요약하자면 이렇습니다.

1. 모든 행성을 방문해야 한다.
2. 지구에서만 속도를 낼 수 있다.
3. 행성을 방문하려면 양의 정수배에 해당하는 속도로 도착해야 한다.
4. 속도는 원하는 대로 줄일 수 있다.

즉 모든 행성을 방문할 수 있는 초기 속도가 문제에서 요구하는 출력입니다.

코드

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int n;
ll answer;
vector<int> v;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    v = vector<int>(n);
    for (int &i : v)
    {
        cin >> i;
    }

    answer = v[n - 1];

    for (int i = n - 2; i >= 0; --i)
    {
        ll quotient = answer / v[i];

        if (answer % v[i])
        {
            ++quotient;
        }

        answer = quotient * v[i];
    }

    cout << answer;
    return 0;
}

풀이

20등 밖이지만 그래도 푼 사람이 많기에 기록해 봤습니다.

예제 입력 1의 과정을 적어보면 이렇습니다.
900, 800, 500, 400, 300
이를 뒤에서부터 살펴보면 해답을 얻을 수 있습니다.

행성 5에 도달하기 위해선 마지막에 꼭 300이 필요합니다.
행성 4에 도달하기 위해선 400이 필요합니다.
행성 3은 500이 필요합니다.
행성 2의 경우에는 400의 배수가 필요한데 추후 500이 필요하기에 500보다 큰 800이 필요합니다.
행성 1은 300의 배수가 필요하고 800보다 커야 하기에 900이 필요합니다.

즉 i의 행성은 i+1의 행성의 속도에 영향을 받습니다.
맨 뒤에서부터 i+1보다 크면서 i의 배수인 값을 구해내면 됩니다.