https://www.acmicpc.net/problem/9020
골드바흐의 추측을 구현하는 문제.
언제나 그렇듯 에라토스테네스의 체를 범위에 맞게 만든 후에, 조건에 맞는 골드바흐 파티션을 찾으면 된다.
파티션이 여러개 존재하는 경우 그 차이가 제일 적은 파티션을 출력해야 하는데, 이를 어떻게 처리할까 하다가, 처음부터 주어진 수의 절반값에서 시작하여 그 차이를 벌려가다가 파티션이 발견되면 끝내는 방식으로 접근하면 됐다.
#include <stdio.h>
int main () {
int seive[10001] = {0, 0};
for (int i = 2; i < 10001; i++) {
seive[i] = 1;
}
for (int i = 2; i < 10001; i++) {
if (seive[i]) {
for (int p = 2; i*p < 10001; p++) {
seive[i*p] = 0;
}
}
}
int T, n, gold_part;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
gold_part = n >> 1; // 절반값
while (gold_part) {
if (seive[gold_part] && seive[n - gold_part]) // 골드바흐 파티션이 발견됨
break;
else
gold_part--;
}
printf("%d %d\n", gold_part, n - gold_part);
}
return 0;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2798번 C언어 풀이 (0) | 2021.09.19 |
---|---|
백준 10253번 C언어 풀이 (0) | 2021.09.19 |
백준 2914번 C언어 풀이 (0) | 2021.09.15 |
백준 11653번 C언어 풀이 (0) | 2021.09.14 |
백준 15829번 C언어 / C++ 풀이 (4) | 2021.09.13 |