[boj] 9020. 골드바흐의 추측 (node.js)
문제 요약
[boj] 9020. 골드바흐의 추측 (node.js)
- 골드바흐의 추측은 정수론 개념 중 하나로, '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.'를 뜻한다.
- 주어진 짝수에 대해 골드바흐의 추측을 만족하는 두 소수를 골드바흐 파티션이라고 할 때, 주어진 수에 대한 골드바흐 파티션을 구하는 문제.
풀이
- 문제에 입력 범위가 제시되어 있으므로, 에라토스테네스의 체를 이용해서 소수를 모두 구한다. 나는
cand[인덱스] == 1 이면 소수
로 배열 인덱스 값을 통해 구분 가능하도록 했다. - 테스트케이스에 대해 while 문으로 답을 구한다.
- 주어진 수를 n이라 할 때, n에 대한 골드바흐 파티션이 여러 개일 경우, 두 수의 차가 가장 작은 조합을 출력하므로 인덱스가 n/2 일 때부터 소수 여부를 파악한다.
- 이때 소수이면 n에서 이 소수를 뺀 숫자도 소수여야 하므로 해당 조건을 만족하면 정답을 구한 것이므로 break
- 소수가 아니면 값을 중간값에서 더 멀리하여 다시 탐색한다. (문제에 의해 답은 무조건 존재하므로)
- 주어진 수를 n이라 할 때, n에 대한 골드바흐 파티션이 여러 개일 경우, 두 수의 차가 가장 작은 조합을 출력하므로 인덱스가 n/2 일 때부터 소수 여부를 파악한다.
내 풀이
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const solution = () => {
let cand = new Array(10000 + 1).fill(1);
for (let i = 0; i <= 10000; i++) {
if (i == 0 || i == 1) {
cand[i] = 0;
continue;
}
for (let j = 2; i * j <= 10000; j++) {
if (cand[i * j] == 0) continue;
cand[i * j] = 0;
}
}
let results = [];
let T = input();
for (let i = 0; i < T; i++) {
let n = Number(input());
let [a, b] = func(n);
results.push(a + " " + b);
}
console.log(results.join("\n"));
function func(X) {
let val;
let mid = Math.floor(X / 2);
while (!val) {
if (cand[mid] && cand[X - mid]) {
val = Math.min(mid, X - mid);
} else {
mid--;
}
}
return [val, X - val];
}
};
let _line = 0;
const input = () => stdin[_line++];
let stdin = [];
rl.on("line", function (line) {
stdin.push(line);
}).on("close", function () {
solution();
process.exit();
});
주절주절
- 문제 초반에 탐색으로 접근해야겠다는 막연한 생각이 들었고, 아무 생각 없이 손에 익은 이분 탐색을 구현해버렸다. 그런데 다시 꼼꼼히 코드를 살펴보니 그렇게 접근한 덕택에 이분탐색 알고리즘의 뼈대인 while 문 내부에서 값을 효율적으로 탐색하는 로직을 구현할 수 있었다! 덕분에 시간복잡도의 무리 없이 깔끔하게 풀 수 있었던 운 좋은 경험이었다.
Author And Source
이 문제에 관하여([boj] 9020. 골드바흐의 추측 (node.js)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@greenish0902/boj-9020.-골드바흐의-추측-node.js저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)