[Java] 백준 14232번 : 보석 도둑

문제

14232번: 보석 도둑

---

 

접근 방법

1. 1보다 크면서 보석을 제일 많이 가져올 수 있게 소인수분해를 생각했습니다.

2. 2부터 탐색하며 나누어 주면서 보석을 결정해줍니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static long K;
    private static int count = 0;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

    //실행
    public static void process() {
        long tmp = K;

        //소인수분해 구하기
        for(long i = 2 ; i*i < K+1 ; i++){
            while(tmp % i == 0){
                sb.append(i+" ");
                count++;
                tmp /= i;
            }
        }

        if(tmp != 1){
            sb.append(tmp);
            count++;
        }

        System.out.println(count);
        System.out.println(sb.toString());
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}