[BOJ][실2][17451] 평행 우주

문제 링크

문제링크

첫 번째 풀이 : Greedy

알고리즘

지구를 벗어나면 속도를 떨어뜨릴 수 있을 뿐 높일 수는 없다.

입력받은 숫자들을 거꾸로 확인하면서 값을 키워야 합니다.

9 8 7 6 5를 입력받은 경우 5 6 7 8 9 순서대로 확인하며 9가 정답입니다.

지구의 속도가 통과속도보다 더 느리면 통과속도로 올리고,
지구의 속도가 더 크면서 정수배면 그냥 통과할 수 있습니다.
지구의 속도가 더 크면서 정수배가 아닌 경우만 고려해주면 됩니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 101;

//int dp[MAX][MAX];
//bool visited[MAX][MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

//void show(void);
//void bfs(int x, int y);

vector<ll> v(300000);

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    ll a = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[n - 1 - i];
    }
    for (int i = 0; i < n; i++) {
        if (ans <= v[i]) ans = max(ans, v[i]);
        else if (ans % v[i] == 0) {
            continue;
        }else {
            ans = (ans / v[i] + 1) * v[i];
        }
    }
    cout << ans;
    return 0;
}

Success Notice: 수고하셨습니다.