2022년이 아름다웠던 이유 (feat. 백준, 27065번)

2022년이 아름다웠던 이유
https://www.acmicpc.net/problem/27065

27065번: 2022년이 아름다웠던 이유

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
vector<int> arr;
int dp[5001];       // 1 : 부족수, 2 : 완전수, 3 : 과잉수
vector<int> getNumbers(int target_number){
    vector<int> temp;
    for(register int i = 1; i <= sqrt(target_number); ++i){
        if(target_number % i == 0){
            if(i * i == target_number)
                temp.push_back(i);
            else
                temp.push_back(i), temp.push_back(target_number / i);
        }
    }
    return temp;
}
bool calcNumbers(int target_number, vector<int> arr){          // 과잉수면 true
    register int sum = 0;
    bool ret = false;
    for(auto value : arr)
        if(value != target_number)
            sum += value;
    if(sum < target_number)
        dp[target_number] = 1;
    else if(sum == target_number)
        dp[target_number] = 2;
    else
        dp[target_number] = 3, ret = true;
    return ret;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    memset(dp, 0, sizeof(dp));
    register int T, N;
    cin >> T;
    for(register int t = 0; t < T; ++t){
        cin >> N;
        auto arr = getNumbers(N);
        if((dp[N] != 0 && dp[N] != 3) || (dp[N] == 0 && !calcNumbers(N, arr)))        // 과잉수가 아님
            cout << "BOJ 2022" << "\n";
        else{
            bool check = true;
            for(auto value : arr)
                if(value != N){
                    if((dp[value] == 3) ||
                    (dp[value] == 0 && calcNumbers(value, getNumbers(value)))){          // 과잉수면 탈락
                        cout << "BOJ 2022" << "\n";
                        check = false;
                        break;
                    }
                }
            if(check){
                cout << "Good Bye" << "\n";
            }
        }
    }
    return 0;
}
// *&)*@*

 

반응형

 

1. 최초 문제에서 주어진 N에 대한 약수를 구합니다.
2. 약수 중 N을 제외한 나머지 수를 연산합니다.
3. 연산된 결과를 dp에 저장하고 조건에 따라 출력을 달리합니다. (N이 부족수라면 dp[N]은 부족수 라고 기록합니다.)