[Baekjoon] 2312_수 복원하기

Silver III

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

---

< 수 복원하기 >

 

문제 풀이 

 

소인수분해를 통해 각 인수와 그 인수가 곱해진 횟수를 출력한다.

 

 my solution (Java)

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

public class _2312_ { // 수 복원하기

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

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int num = Integer.parseInt(bf.readLine());

			int idx = 2;
			int cnt = 0;
			while (idx <= num) {
				if (num % idx == 0) {
					num /= idx;
					cnt += 1;
				} else {
					if (cnt > 0) {
						bw.write(idx + " " + cnt + "\n");
						cnt = 0;
					}
					idx++;
				}
			}
			if (cnt > 0) {
				bw.write(idx + " " + cnt + "\n");
			}
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 수
num : 양의 정수 N
idx : 인수
cnt : 인수가 곱해진 횟수

 

테스트 케이스 수를 입력받는다. 테스트 케이스 수만큼 양의 정수를 입력받은 후 소인수분해를 한다. 인수가 증가하는 순으로 출력해야 하므로 소인수분해를 구할 때 2부터 시작한다. 정수를 idx로 나눌 수 있으면 인수라는 뜻이므로 나누고 cnt를 증가시킨다. 나눌 수 없다면 다음 인수를 구해야 하므로 인수와 횟수를 출력 후 idx를 증가시킨다. 

 

* 곱해진 횟수가 0인 것은 출력하면 안 된다는 것을 주의해야 한다. 

---

---