[BOJ] 1153_네 개의 소수

네 개의 소수

문제 링크: https://www.acmicpc.net/problem/1153

1153번: 네 개의 소수

 

전체 소수를 구하고 소수 하나씩 총 4개를 모두 더해본다.
그리고 같으면 그 4개의 소수를 출력하고 4중 for문을 빠져나오고 끝낸다.
하지만 같은 값을 찾지 못할 경우 -1을 출력한다.

단순히 여기까지 하면 시간 초과이다.
따라서, 첫번째 요소와 두번째 요소를 더했을 때 입력값 n을 초과하는지, 또 1,2,3번째 요소를 더했을 때 n을 초과하는지 마지막으로 모두 더했을 때 n을 초과하는지 판단한다.
초과할 경우 현재 단계의 for문은 그만돌린다. 이유는 어차피 현재보다 다음 값을 더해나가기 때문에 적어도 현재 값보다 더 클 것이기 때문이다.

 

• 정답코드

    #include<iostream>
    #include<vector>
    using namespace std;
  
    #define maxNum 1000001
  
    int primeNumber[maxNum];
    vector<int> primeNumList;
  
    void setPrime() {
        for (int i = 2; i < maxNum; i++) {
            primeNumber[i] = i;
        }
  
        for (int i = 2; i < maxNum; i++) {
            if (primeNumber[i] == 0) continue;
  
            for (int j = 2 * i; j < maxNum; j += i) {
                primeNumber[j] = 0;
            }
        }
        for (int i = 2; i < maxNum; i++) {
            if (primeNumber[i] != 0)
                primeNumList.push_back(i);
        }
    }
  
    int main() {
        setPrime();
  
        int n;
        cin >> n;
        bool flag = true;
        for (int a = 0; a < primeNumList.size() && flag; a++) {
            for (int b = a; b < primeNumList.size() && flag; b++) {
                int first = primeNumList[a] + primeNumList[b];
                if (first >= n)
                    break;
                for (int c = b; c < primeNumList.size() && flag; c++) {
                    int second = first + primeNumList[c];
                    if (second >= n)
                        break;
                    for (int d = c; d < primeNumList.size() && flag; d++) {
                        int third = second + primeNumList[d];
                        if (third > n)
                            break;
                        if (n == primeNumList[a] + primeNumList[b] + primeNumList[c] + primeNumList[d]) {
                            cout << primeNumList[a] << ' ' << primeNumList[b] << ' ' << primeNumList[c] << ' ' << primeNumList[d];
                            flag = false;
                        }
                    }
                }
            }
        }
        if (flag)
            cout << -1;
  
        return 0;
    }