[C] 백준 2090번 : 골드바흐의 추측

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

9020번: 골드바흐의 추측

시간이 0.5초나 되는 코드입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int isPrimeNumber(int x);	//소수 판별 함수 선언

int main() {
	int N, T, x = 0;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &N);
		int* arr = (int*)malloc(sizeof(int) * (N + 1));	//배열의 index를 실제 값으로 생각할 것이기 때문에 배열의 크기는 (N+1)
		for (int j = 2; j <= N / 2; j++) {	// N / 2까지 범위를 설정함으로써 j <= (N - j)가 성립되어 작은 소수부터 출력
			arr[j] = isPrimeNumber(j);	//isPrimeNumber함수에 의해 index가 소수라면 배열의 값을 1로 초기화
			if (arr[j] == 1 && isPrimeNumber(N - j) == 1)	//j가 소수로 확정났다면 다른 한 수 N-j만 소수면 됨
				x = j;										//반복문이 계속 돌기 때문에 결국 합을 구성하는 소수의 차가 가장 적게 될 것.
		}
		printf("%d %d\n",x, N - x);
		free(arr);	//1차원 배열 동적할당 해제
	}

	return 0;
}


int isPrimeNumber(int x) {
	double length;
	length = sqrt(x);
	for (int i = 2; i <= length; i++) {
		if (x % i == 0) return 0;	//소수가 아니면 0을 리턴
	}
	return 1;	//소수는 1을 리턴
}

자꾸 시간초과가 나서 애먹은 문제입니다.

반드시 이중반복문으로 풀어야합니다. 삼중반복문으로 코드를 구성한다면 시간초과가 나타납니다.삼중반복문을 쓰지 않고 어떻게 풀어야하지?가 주된 고민이었습니다.

 

1. N+1개 만큼의 일차원배열을 동적할당하여 소수라면 배열의 값을 1로 초기화하였고 배열의 인덱스로 어떤 수인지 구분할 수 있도록 하였습니다.(12번줄)

 

2. 2~N/2까지 반복문을 돌려 그 수가 소수인지 판별하는 함수를 이용하여 소수를 판별하였습니다.

여기서 삼중반복문으로 가지않으려면 판별에서 끝내면 안되었습니다.

 

 N에 대한 두 소수의 합을 구하는 문제이기 때문에

하나의 수를 구했을 경우, 나머지 수는 자연스럽게 n-(구해진수)로 고정시킬 수 있었습니다.

=> O(n^2) > O(n)으로 시간복잡도 감소

 

위 아이디어를 이용하여  isPrimeNumber(j)가 소수라고 판별되었다면 N-j가 소수인지 바로 판별을 해줍니다.

N-j도 소수라면 정답의 후보가 됩니다.

반복문의 루프는 계속 N/2까지 돌기 때문에 결국 마지막에 변수 x에 저장되는 값이 두 소수의 차가 가장 적을 때일 것입니다.

-> 범위가 N/2인 이유는 j가 N - j보다 커지는 상황을 미연에 방지하기 위해서 입니다.

 

0.5초나 걸려 0.1초 미만으로 코드를 짜신 분을 찾아보았다.

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    for (int t = 0;t < T;t++) {
        int n;
        scanf("%d", &n);
        int i, j;
        int arr[10001] = { 1,1, };

        for (i = 2; i * i <= 10001; i++)
            if (arr[i] == 0)
                for (j = i * i; j <= 10001; j += i)
                    arr[j] = 1;

        int l = n / 2, r = n / 2;
        while (1) {
            if (arr[l] == 0 && arr[r] == 0) {
                printf("%d %d\n", l, r);
                break;
            }
            l--;
            r++;
        }
    }
    return 0;
}	yacyj님의 코드

N의 범위가 크지 않은 10,000으로 주어졌었던 것을 생각하면 굳이 동적할당할 이유가 없었다.

while문이 굉장히 인상적이었는데 저렇게도 할 수 있겠구나..하는 생각도 들었다.