[ BOJ - 27065번 ] 2022년이 아름다웠던 이유 (C++)

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

 

 n <= 5000 이므로, O(log n²)의 시간복잡도를 가질 수 있다.

 따라서, DP를 이용해 5000까지의 모든 수에 대해

1. 부족수 or 완전수(0),
2. 약수 중 과잉 수가 있는 과잉수(1),
3. 약수 중 과잉수가 없는 과잉수(2)로 미리 판별해놓고,

입력된 값에 대해 2가 저장되어 있다면 "Good Bye",

0 or 1이 저장되어 있다면 "BOJ 2022"를 출력해 문제를 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    iostream::sync_with_stdio(0);
    cin.tie(0);

    vector<int> dp(5001);

    for (int i = 2; i <= 5000; i++) {
        int sum = 0;
        bool flag = true;
        for (int j = 1; j < i; j++) {
            if(i%j == 0) {
                sum += j;
                if(dp[j]) {
                    flag = false;
                }
            }
        }
        if (sum > i) {
            if (flag) {
                dp[i] = 2;
            } else {
                dp[i] = 1;
            }
        }
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if(dp[num] == 2) {
            cout << "Good Bye" << '\n';
        } else {
            cout << "BOJ 2022" << '\n';
        }
    }

    return 0;
}