[c/c++] 백준 9020 (Silver 2)

🔨 문제

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

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다.

또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n(4 ≤ n ≤ 10,000)이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

🔨 해결방법

쓰린 아픔이 있는 문제..
내가 간식을 먹고, 저녁을 먹고 와서 봐도 시간 초과가 해결되지 않았다..

여기에서 가장 중요한 건 누가 봐도 2중 for문을 돌려야 하는데 그 값의 시작점과 끝을 어떻게 놓을 것인가!!! 이것이 시간초과를 막기 위한 유일한 방법(물론 내 기준)

처음에 나는 i=2부터 시작해서 2중 for문으로 안쪽의 for문을 1씩 증가시켜서 입력값과 일치하고 가장 최소의 크기이면 결과값을 출력하는 식으로 알고리즘을 짰는데 계속 시간초과가 나왔다.

하지만 내가 생각해도 시간초과가 나올법한 코드로 계속 수정하고 있었다.

for (int i = n/2; i >=2; i--) 

우리가 30까지 소수를 생각해보면
2/ 3/ 5/ 7/ 11/ 13/ 17/ 19/ 23/ 29 인데 내 코드에서 이들은 인덱스가 곧 값이다.

예를 들어 입력이 8이 들어왔을 경우 골드바흐의 파티션에 들어올 수 있는 result1과 result2는 더하였을 때 8이어야 하는데 이 두 수는 동시에 4보다 더 큰 값을 가질 수 없다. 그래서 애초에 시작선부터 i=n/2으로 시작하고 점점 줄여주는 쪽으로 코드를 만들어줘야 한다.

🔨 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[10000] = { 0 };

void check(int start) {

    int result[2] = { 0 };	// 결과 저장용 배열(굳이 배열 사용할 필요는 없다.)
    int min = 10000;	// 골드바흐의 파티션의 두 소수의 차이가 가장 적어야 하므로 구분용 변수 선언
    for (int i = n/2; i >=2; i--) {
        if (arr[i] == 0) continue;	// 소수가 아니면 pass
        int cnt = 0;	// 파티션 크기 비교용 변수
        for (int j = i; j <= n; j++) {
            cnt++;	
            if (n < arr[j]) break;	// 입력값보다 배열의 값이 더 크다면 break
            if (min <= cnt) break;	// 소수의 차이 비교 
            if (arr[i] + arr[j] == n) {	// 입력값과 같아진다면
                if (cnt < min) {
                    min = cnt;	// 카운트값을 min에다가 넣어주고 
                    result[0] = arr[i];	// 출력할 대상에 저장
                    result[1] = arr[j];
                }

            }
        }
    }

    cout << result[0] << ' ' << result[1] << '\n';
}

int main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;

    for (int i = 2; i <= 10000; i++) {
        arr[i] = i;
    }

    for (int i = 2; i <= 10000; i++) {
        if (arr[i] == 0) continue;
        else {
            for (int j = i * 2; j <= 10000; j += i) {
                arr[j] = 0;
            }
        }
    }

    while (t > 0) {
        cin >> n;
        check(n);
        t--;
    }
    return 0;
}