[백준 9020] 골드바흐의 추측

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

9020번: 골드바흐의 추측

#include <stdio.h>
#include <math.h>
void guess(int gb)
{
	int res;
	int flag_i, flag_r;
	int min = 10000 - 4, sub, min_i, min_r;

	for (int i = 2; i < gb; i++) {	//두 수 구하기 i & i와 더해서 gb가 되는 res
		res = gb - i;				
		flag_i = 0, flag_r = 0;		//각 숫자마다 플래그 초기화 필요
		//printf("%d %d\n", i, res);	//debug
		for (int j = 2; j < gb - 1; j++) {		//두 수가 소수인지 판별
			if (j * j > gb) break;			//타임아웃 방지
			if ((j < i) && !(i % j)) {
				flag_i = 1;
				break;
			}
			if ((j < res) && !(res % j)) {
				flag_r = 1;
				break;
			}
		}
		//printf("%d %d\n", flag_i, flag_r);	//debug
		if ((flag_i == 0) && (flag_r == 0)) {
			sub = abs(i - res);
			if (sub < min) {	//골드바흐 파티션의 거리가 최소인 것을 찾음
				min = sub;
				min_i = i;
				min_r = res;
			}
		}
	}
	printf("%d %d\n", min_i, min_r);
}

int main(void)
{
	int n, gb;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &gb);
		guess(gb);
	}
	return 0;
}

기존 소수찾는 문제와는 다르게 생각할 것이 좀 있었다. 

1. 일단 해당 숫자를 이루는 두 수를 찾아야 한다. 

2. 두 수가 소수인지 판별해야 한다. 

3. 해당 숫자를 이루는 두 수(골드바흐 파티션)가 여러 개인 경우, 두 수의 차이가 가장 작은 것을 선택한다. 

 

(1)번의 과정은 for문 한개를 돌리면서 i 와 res( = gb - i)로 표현해주었다.

(2)번의 과정은 기존 소수 찾는 문제와 동일하게 플래그를 통해 구현했다. 

내가 자주하는 실수를 또 했었는데, 각각의 i와 res에 대하여 플래그를 초기화 해주어야 한다는 점 !! 명심하자.

두 숫자가 소수인지 판별하는 것은 두번째 for문으로 구현했고, 만약 j 가 i나 res 의 약수가 되면 바로 루프를 빠져나오도록 했다. 그럼에도 불구하고 타임아웃이 났었는데, 이는 역시나 if (j * j > gb) break; 조건으로 해결할 수 있었다. 

(3)번의 과정은 최대한 라이브러리 안쓰고 싶었는데, 코드가 더 길어지는 것을 방지하고자.. math.h의 abs를 써서 두 수의 차이의 절댓값을 구해주었다. 이를 min과 비교하여 더 작으면 각각의 i와 res를 저장하도록 구현했다.