[백준] 11502번 세 개의 소수 문제 (C++)

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

 

 

홀수 K를 입력받은 후 3개의 소수를 더해서 K를 만들어야 하는 문제이다.

 

K의 범위가 1 ~ 1000밖에 안되기 때문에

 

1 ~ 1000의 소수를 구하고 구한 수들을 중복허용하여 모든 경우의 수를 구해서 값이 만들어지는지 확인하면 된다.

 

따라서 3중 for문을 사용하여 구하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int T, N;
int arr[1001];
vector<int> v;

void solve() {
    for(int i = 0; i < v.size(); i++) {
        for(int j = 0; j < v.size(); j++) {
            for(int k = 0; k < v.size(); k++) {
                if(v[i] + v[j] + v[k] == N) {
                    cout << v[i] << " " << v[j] << " " << v[k] << endl;
                    return;
                }
            }
        }
    }

    cout << 0 << endl;
}

void Init() {
    arr[0] = true;
    arr[1] = true;

    for(int i = 2; i <= 1000; i++) {
        if(!arr[i]) {
            for(int j = i + i; j <= 1000; j += i) {
                arr[j] = true;
            }
        }
    }

    for(int i = 2; i <= 1000; i++) {
        if(!arr[i]) {
            v.push_back(i);
        }
    }
}

void input() {
    cin >> T;

    Init();

    while(T--) {
        cin >> N;

        solve();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}