[Baekjoon] 14232_보석 도둑

Silver I

문제(출처: https://www.acmicpc.net/problem/14232)

---

< 보석 도둑 >

 

문제 풀이 

 

효율적으로 약수를 찾는 알고리즘을 찾아보니 구하려는 수의 제곱근까지 수만 0으로 나누어 떨어지는지 확인하면 된다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class _14232_ { // 보석 도둑

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		Long k = Long.parseLong(bf.readLine());

		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 2; i <= Math.sqrt(k) + 1; i++) {
			while (k%i == 0) {
				list.add(i);
				k/=i;
			}
		}

		if (k > 1) {
			bw.write(list.size() + 1 + "\n");
		} else {
			bw.write(list.size() + "\n");
		}

		for (int i = 0; i < list.size(); i++) {
			bw.write(list.get(i) + " ");
		}
		if (k > 1) {
			bw.write(k + "");
		}

		bw.flush();
	}
}

변수)
k : 들 수 있는 무게
list : 훔쳐올 보석들의 무게

 

들 수 있는 무게 k를 입력받는다. 2부터 (k의 제곱근+1)까지 탐색하여 약수를 찾는다. k가 i로 나눠진다면 나누고 list에 i를 저장한다. i로 나눠지지 않을 때까지 반복한다.

 

만약 위의 과정을 다 끝낸 후 k값이 1보다 크다면 list 크기 +1을 출력한다. k값이 1이라면 list 크기를 출력한다. list를 순환하면서 값을 출력하고 마지막에 k값이 1보다 클 때 k값을 출력한다.

---

---