백준 11502번 - 세 개의 소수 문제(Node.js)

백준 11502번 - 세 개의 소수 문제(Node.js)

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

11502번: 세 개의 소수 문제

 

• 알고리즘 분류 : 수학  브루트포스  알고리즘  정수론  소수 판정  에라토스테네스의 체

 

 

---

나의 풀이

	const readline = require("readline");
	const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
	});
	let input = [];
	let primeNum = [];
	rl.on("line", function (line) {
	input.push(line);
	T = Number(input[0]);
	if (input.length - 1 === T) {
	rl.close();
	}
	}).on("close", function () {
	let testCase = [];
	for (let i = 0; i < T; i++) {
	testCase[i] = Number(input[i + 1]);
	}
	FindPrimeNum();
	for (let i = 0; i < T; i++) {
	let finished = false;
	for (let j = 0; j < testCase[i]; j++) {
	for (let k = 0; k < testCase[i]; k++) {
	for (let l = 0; l < testCase[i]; l++) {
	if (primeNum[j] + primeNum[k] + primeNum[l] === testCase[i]) {
	finished = true;
	console.log(primeNum[j], primeNum[k], primeNum[l]);
	break;
	}
	}
	if (finished) {
	break;
	}
	}
	if (finished) {
	break;
	}
	}
	if (!finished) {
	console.log(0);
	}
	}
	process.exit();
	});
	// 1 ~ 1000 사이의 소수 구하기
	function FindPrimeNum() {
	for (let i = 2; i <= 1000; i++) {
	let isPrime = true;
	for (let j = 2; j < i; j++) {
	if (i % j === 0) {
	isPrime = false;
	}
	}
	if (isPrime) {
	primeNum.push(i);
	}
	}
	return primeNum;
	}

view raw 11502.js hosted with ❤ by GitHub

• 제출 시 결과는 맞았습니다!!
• 57 ~ 73번째 줄 : FindPrimeNum() 함수는 1 ~ 1000 범위의 숫자들 중 소수를 구하는 함수이다.
        ┌ 소수는 자기 자신과 1로만 나누어지는 수라는 특징을 이용하여
        └ 이중 for문과 bool 타입을 가지는 isPrime을 사용하여 1 ~ 1000 범위의 소수를 구했다.
• 28 ~ 51번째 줄 : 세 개의 소수의 합으로 각 Test Case를 만들 수 있는 경우의 수를 구한다.
        ┌ 문제 조건 중 여러 개의 답이 가능하다면 그중 하나만 출력해도 되므로,
        ├ 처음 세 개의 소수의 합으로 각 Test Case를 만들 수 있다면, 그것을 바로 출력하도록 했다.
        └ 다른 경우의 수가 출력되는 것을 막기 위하여 bool Type의 finished를 이용하였다.

 

 

---

느낀점

• 에라토스테네스의 체를 알아야 n까지 범위의 소수를 손쉽게 구할 수 있는 문제인 것 같다.
• for문을 4번이나 돌려서 RunTime Error가 뜰 줄 알았지만, Test Case가 1000까지이기 때문에 Error가 발생하지 않는 것 같다.
• 마찬가지로, 브루트포스 알고리즘에 해당되기 때문에 for문을 여러번 돌려서 푸는게 맞다고 생각하지만, 더 깔끔하고 쉽게 푸는 방법이 있지 않을까 더 연구해봐야될 것 같다..