백준 알고리즘 9020번: 골드바흐의 추측 C언어

문제 출처: https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

1. 코드

#include <stdio.h>

int main(void)
{
    int cnt, N;
    int i, j, arr[10001] = {0, };
    
    for(j = 2; j < 10001 / j; j++)
    {
        if(!arr[j])
        {
            for(i = j * j; i < 10001; i += j)
                if(i % j == 0) arr[i] = 1;
        }
    }
    
    scanf("%d", &cnt);
    while(cnt--)
    {
        scanf("%d", &N);
        for(i = N / 2; i > 1; i--)
        {
            if(arr[i] == 1) continue;
            for(j = N / 2; j <= N; j++)
            {
                if(arr[j] == 1) continue;
                if(i + j == N) goto OUT;
            }
        }
        OUT: printf("%d %d\n", i, j);
    }
    return 0;
}

2. 문제 해결 방식

먼저 배열을 통해 소수인지 판별한다. 이 과정은 다른 글에 많이 써놨으니 그 글을 참고하길 바란다.

참고 글: https://travelerfootprint.tistory.com/48

백준 알고리즘 2581번 : 소수 C언어

그리고 반복 횟수를 입력받고 요구하는 숫자를 입력받은 다음에 이곳의 연산이 이 문제의 핵심이다. 정확히 수를 반으로 나눈 다음에 가운데부터 시작해서 점점 바깥쪽으로 이동하며 계산하면 손쉽게 시간 초과 에러가 생기지 않고 깔끔하게 끝낼 수 있다. 그런데 가운데부터 시작하면 i의 값과 j값의 합이 N과 같을 때 바로 2중 반복문을 빠져나와야 한다. 왜냐하면 10 같은 경우 3 + 7 = 10, 5 + 5 = 10이기에 답으로 3 7이 나오면 틀리기 때문에 goto 문을 이용하여 2중 반복문을 빠져나온다.

개인적으로 반복문에서 나올 때는 break 문을 선호하지만 이렇게 break 문을 두 번 써야 하는 경우에는 goto 문이 유용한 것 같다. 

3. 느낀 점

말이 씨가 된다고 하던가 지난번 글에서 소수 구하는 것 말고 다른 요소들이 어려웠으면 좋겠으면 하는 마음으로 쓴 글이 있는데 이 문제는 다른 문제에 비해 조금 어려웠다. 문제 자체는 간단하지만 수가 커질수록 시간 초과 에러에 대해 고민해야 해서 그 문제를 해결하고 초반에는 2중 반복문 나오는데 break 문을 2번 쓰기 싫어서 구글링을 10분 정도 해서 찾은 goto 문의 활용이었다. 솔직히 코딩을 하는데 goto 문이 전혀 쓸 곳이 없다고 생각하고 실제로 많이 사용하지 않아서 기억 한 구석에 흐려지고 있었는데 이번 문제를 통해 goto 문이 이러한 상황에서 활용한다는 것을 깨달았다.

그래도 이 문제 또한 해결해서 다행이다.