BOJ_14232_보석 도둑 (Java)

[Silver I] 보석 도둑 - 14232

문제 링크

성능 요약

메모리: 14368 KB, 시간: 116 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2025년 3월 14일 15:03:12

문제 설명

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

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

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

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

입력

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

출력

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

문제 풀이

무조건 K만큼 들어야하므로 나눗셈을 적용했다. 나눌 수 없는수는 소수이므로 소수로 계속 나누어주었다.

코드

package BOJ_14232_보석도둑;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static long K;
    static List<Long> elements = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_14232_보석도둑/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        K = Long.parseLong(br.readLine());

        long cnt = 0;
        long num = K;

        for (long i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                elements.add(i);
                num /= i;
                cnt++;
            }
        }

        if (num > 1) {
            elements.add(num);
            cnt++;
        }

        Collections.sort(elements);

        sb.append(cnt).append("\n");
        for (int i = 0; i < elements.size(); i++) {
            sb.append(elements.get(i)).append(" ");
        }
        System.out.println(sb.toString());
        br.close();
    }
}