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

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

문제

보석 도둑 문제 링크

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

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

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

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

입력

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

7 3

출력

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

2
3 5

접근 방식

2부터 계속 k와 나누어 떨어지는 수를 찾아 출력하되 k의 제곱근 까지 탐색 하고 이후 k가 아직 1이 아니라면 k를 마지막으로 출력한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main_G5_14232 {

	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long k = Long.parseLong(br.readLine());
		
		int c = 2;
		int cnt = 0;
		List<String> list = new ArrayList<>();
		while(k != 1) {
			if (c>=1000000) {
				list.add(k+"");
				cnt++;
				break;
			}
			if (k % c == 0) {
				k/=c;
				cnt++;
				list.add(c+"");
			}
			else {
				c++;
			}
		}
		
		
		System.out.println(cnt);
		System.out.println(String.join(" ", list));
		
	}
	
	

}