백준 20946 - 합성인수분해 (C++)

문제

• 문제 링크

  
   BOJ 20946 - 합성인수분해 
  

• 문제 요약

자연수 $N$이 주어진다.
이 수의 '합성인수분해' 를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10^{12}$

알고리즘 분류

• 수학(math)
• 정수론(number theory)
• 그리디 알고리즘(greedy)

풀이

소수로 표현하는 소인수분해가 아닌 합성인수분해라니.. 꽤 흥미로운 문제 같다.

적당한 수 몇 개를 가지고 놀아보면 알겠지만,
결국 나열되는 합성수들이 단조성을 가지려면 소인수들의 곱으로 한 쌍씩 묶어주는 것이 최적임을 알 수 있다.
단, 나열되는 소인수들은 단조 증가 하여야 한다.

이에 따라 합성인수분해가 불가능 한 경우는 소인수가 하나일 때 즉, 소수일 때가 불가능 한 경우가 되겠다.

한가지 주의할 점으로, 소인수가 홀수 개일 때는 끄트머리 $3$개를 묶는 게 최적임이 자명하다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
    vector <ll> V;
    ll n, i, j; cin >> n;
    for (i = 2, j = n; j > 1 && i * i <= n; i++)
        if (!(j % i))
            V.push_back(i), j /= i--;
    if (j > 1) V.push_back(j);
    if (V.size() < 2) cout << -1;
    else
        for (i = 1; i < V.size(); i += 2)
            cout << (V[i] * V[i - 1] * (i == V.size() - 2 ? V[i + 1] : 1)) << ' ';
}

comment

끝