[백준] 14232번 : 보석 도둑 (C++)

14232번 : 보석 도둑

---

문제)

희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 훔쳐갈 시, 보석끼리 달라붙으며 무게가 모든 보석들의 곱으로 늘어난다.

 

효빈이는 이 보안장치를 해제할 수 없기 때문에, 차라리 곱해진 대로 최대한 많은 보석들을 가져오기로 계획했다. 효빈이는 한번에 k라는 무게를 들 수 있으므로, 딱 k만큼의 무게만큼의 보석을 가져오고 싶은데, 그 때 보석들의 최대 개수를 알고싶다.

 

영선상에는 세계 최고의 보석가게답게 모든 무게의 보석들이 매우 많이때문에, 훔쳐가는 보석이 부족할 일은 없다. 다만 모든 보석들은 무게가 1보다 크다.

 

효빈이는 이제 영선상에 잡입할 계획을 다 세웠다. 하지만 무슨 보석들을 훔쳐올지 결정하지 못하였는데, 효빈이를 대신하여 훔쳐올 보석들을 결정해주자.

 

 

 

입력 :

첫째 줄에는 효빈이가 들 수 있는 무게 k가 주어진다.(2≤k≤10^12)

 

 

 

출력 :

첫째 줄에는 효빈이가 훔쳐올 보석의 개수를 출력하고, 다음 줄에는 훔쳐올 보석들의 무게를 오름차순으로 출력하시오.

 

 

 

 

 

풀이)

 

// 14232. 보석 도둑
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    // 소인수분해를 하는 문제
    long long n;
    cin >> n;
 
    // 수가 매우 크므로 long long을 사용한다.
    vector<long long> vec;
 
    // n을 사용하게 되면 for문에서 값이 계속 바뀌므로
    // n을 복사한 x를 사용한다.
 
    long long x = n;
    for (long long i = 2; i * i < n + 1; i++)
    {
        // 소인수 분해를 계속해, 값을 vec에 넣어준다.
        while (x % i == 0)
        {
            vec.push_back(i);
            x /= i;
        }
    }
 
    // 만약 모든 소인수 분해를 마쳤는데도, x가 1이 아니라면
    // 마지막 수가 소수인 것이므로, x를 넣어준다.
    if (x != 1) vec.push_back(x);
 
    cout << vec.size() << "\n";
    for (auto ele : vec) cout << ele << " ";
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/14232 

14232번: 보석 도둑