[백준 JAVA] 14232. 보석 도둑

문제 링크

---

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

접근 방법

---

2부터 시작해서 효빈이가 들 수 있는 무게까지 반복문을 돌립니다.

 

소스 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
		long k = Long.parseLong(br.readLine());
		int cnt = 0;

		for (int i = 2; i <= k; i++) {
			if (i >= 1000000) {
				sb.append(k);
				cnt++;
				break;
			}

			while (k % i == 0) {
				k /= i;
				cnt++;
				sb.append(i).append(" ");
			}
		}

        System.out.println(cnt);
		System.out.println(sb);
	}
}

코드 설명

---

훔칠 수 있는 보석의 무게가 곱이기 때문에 나누어지는지 판단합니다.

나누어진다면 들 수 있는 무게를 줄여줍니다.

소인수를 구하는 것이기 때문에 10⁶까지만 계산하고,

10⁶ 까지 반복문을 돌렸는데도 들 수 있는 무게가 남았다면 훔쳐갈 수 있는 보석 리스트에 추가해 줍니다.

 

처음에는 소인수이면 소수여야 하므로 소수인지부터 확인해 줘야겠다고 생각했었지만

2부터 나눠주기 때문에 그럴 필요가 없다는 것을 깨달았습니다.