BOJ 25344 : 행성 정렬

• 문제 링크 : boj.kr/25344
• 난이도 : S4
• 태그 : 정수론

25344번: 행성 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    ll ans = 1;
    for(int i = 0; i < n-2; i++) {
        ll input;
        cin >> input;
        ans = ans * input / gcd(ans, input);
    }
    cout << ans;

    return 0;
}

---

풀이

문제를 단순화해서 N이 4일 때를 생각해보자.

1, 2, 3, 4번째 행성이 정렬되었다는 것은 2, 3번째 행성이 정렬되었다는 것을 내포한다.

따라서 1, 2, 3번째 행성이 정렬되는 주기와 2, 3, 4번째 행성이 정렬되는 주기를 맞추기 위해,

2, 3번째 행성은 이미 정렬되어 고정되어 있고, 각 주기에 맞춰 1번째 행성과 4번째 행성이 도달해 정렬된다고 생각할 수 있다.

이제 1번째 행성과 4번째 행성이 동시에 2, 3번째 행성의 위치에 도달하는 주기를 찾는 문제로 바뀌게 되고, 이는 두 주기의 최소공배수를 통해 쉽게 구할 수 있다.

 

이제 N을 5로 확장해보자.

1, 2, 3, 4번째 행성이 정렬되는 주기는 위의 방식으로 찾을 수 있다.

마찬가지로 1, 2, 3, 4번째 행성이 정렬되는 주기와 3, 4, 5번째 행성이 졍렬되는 주기를 맞추는 것 또한 3, 4번째 행성이 고정되어 있고, 1, 2번째 행성과 5번째 행성이 도달해 정렬된다고 생각할 수 있다.

따라서 위와 같은 방식으로 주기를 구할 수 있다.

 

최종적으로 모든 주기의 최소공배수를 구해 답을 구할 수 있다.