C++[백준]27065번 2022년이 아름다웠던 이유

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

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

 

솔루션

---

문제 이해가 살짝 난해해서 쉽게 풀지 못했다..ㅎ

 

 어떤 수 N에 대해서

 

먼저 자기 자신을 제외한 약수들의 총합을 더하고, 또 나눠지는 수에 대해서 과잉수인지 아닌지를 판단하는 배열을 만들어서 해결 했다.

 

 

코드

---

#include <iostream>
using namespace std;


//부족or완전이면 1,
//과잉이면 2
int overNum[5002];


//조건에 만족하면 2
//조건에 만족X 1
int is_beauty[5002];

int calcBeauty(int idx) {
	int sum = 1;
	bool is_over = false;
	if (is_beauty[idx] != 0) {
		return is_beauty[idx];
	}
	if (idx == 1) {
		return overNum[idx] = 1;
	}
	else {
		for (int i = 2; i < idx; i++) {
			if (idx % i == 0) {
				sum += i;
				
				//과잉수가 있다고 하면,
				calcBeauty(i);
				if (overNum[i] == 2) {
					is_over = true;
				}
			}
		}
	}

	if (sum > idx) {
		overNum[idx] = 2;
		if (is_over) {
			return is_beauty[idx] = 1;
		}
		else {
			return is_beauty[idx] = 2;
		}
	}
	else {
		overNum[idx] = 1;
		return is_beauty[idx] = 1;
	}
	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tc;
	cin >> tc;

	while (tc--) {
		int N;
		cin >> N;

		calcBeauty(N)==2? (cout<<"Good Bye\n") : (cout<<"BOJ 2022\n");
	}
}