알고스팟 알고리즘: WEIRD [C++]

문제 출처: https://algospot.com/judge/problem/read/WEIRD

algospot.com :: WEIRD

1. 코드

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

using namespace std;

bool flag;
void solve(vector <int> arr, int n, int sum, int cnt)
{
	if (n == sum)	//덧셈 결과 n과 같다면 이상한 숫자 확인
	{
		flag = true;
		return;
	}

	for (int i = cnt; i >= 0; i--)
	{
		if (flag) return;
		if (sum + arr[i] > n) continue;
		solve(arr, n, sum + arr[i], i - 1);
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int c;
	cin >> c;

	while (c--)
	{
		int n, sum = 1;
		vector <int> arr;
		cin >> n;
		arr.push_back(1);
		flag = false;
		for (int i = 2; i * i <= n; i++)		//n의 약수 저장
		{
			if (n % i == 0) {
				arr.push_back(i);
				arr.push_back(n / i);
				sum += i + n / i;
			}
		}
		if (sum <= n) {		//약수의 합이 n보다 작거나 같다면 n은 이상한 숫자가 아니다.
			cout << "not weird" << '\n';
			continue;
		}
		sort(arr.begin(), arr.end());		//약수 저장한 벡터 정렬
		solve(arr, n, 0, arr.size() - 1);	//백트래킹으로 덧셈 진행

		if (flag) cout << "not ";
		cout << "weird" << '\n';
	}
}

(실행)

2. 풀이

해당 문제는 이상한(WEIRD) 숫자를 구하는 문제인데 조건은 두가지이다. 첫번째는 자기자신의 수를 제외한 약수의 합이 자기자신의 수보다 초과하여야하고, 두번째는 자기자신의 수를 제외한 약수의 부분집합의 합이 자기자신의 수와 동일해야 한다.

1. 입력한 수를 구한 뒤 벡터에 저장 후 저장한다.
2. 저장된 값이 n보다 작거나 같으면 이상한(WEIRD) 수가 아니기 떄문에 not weird 라는 메시지 출력 후 continue를 해준다.
3. 약수를 저장한 벡터를 정렬한다.
4. 백트래킹을 이용하여 부분집합의 합이 자기 자신의 수와 동일한지 확인한다.
5. 동일하다면 "not weird"를 출력하고 아니라면 "weird"를 출력한다.

int c;
cin >> c;

while (c--)

테스트 케이스 횟수를 입력한 뒤 그 횟수만큼 반복한다.

int n, sum = 1;
vector <int> arr;
cin >> n;
arr.push_back(1);
flag = false;
for (int i = 2; i * i <= n; i++)		//n의 약수 저장
{
	if (n % i == 0) {
		arr.push_back(i);
		arr.push_back(n / i);
		sum += i + n / i;
	}
}

입력한 수의 약수를 벡터에 저장하면서 sum에도 더해준다.

if (sum <= n) {		//약수의 합이 n보다 작거나 같다면 n은 이상한 숫자가 아니다.
	cout << "not weird" << '\n';
	continue;
}

약수들의 합이 n과 동일하거나 작다면 이상한 수가 아니므로 "not weird" 출력 후 다음 케이스를 확인하기 위해 continue를 해준다.

sort(arr.begin(), arr.end());		//약수 저장한 벡터 정렬
solve(arr, n, 0, arr.size() - 1);	//백트래킹으로 덧셈 진행

벡터를 정렬 후 함수에 값을 전달해주는데

bool flag;
void solve(vector <int> arr, int n, int sum, int cnt)
{
	if (n == sum)	//덧셈 결과 n과 같다면 이상한 숫자 확인
	{
		flag = true;
		return;
	}

	for (int i = cnt; i >= 0; i--)
	{
		if (flag) return;
		if (sum + arr[i] > n) continue;
		solve(arr, n, sum + arr[i], i - 1);
	}
}

solve 함수는 백트래킹 함수이다. n의 값이 sum과 동일할 때까지 반복해주는데 동일하다면 flag 값을 true로 설정해주고 함수를 종료한다. 동일하지 않다면 반복문을 통해 약수의 값 중 가장 큰 값부터 작은 값까지의 부분 집합의 합을 진행한다.

그런데 만약 다음 더해야할 값을 더하게 될 때 입력했던 값보다 커지게 되면 의미가 없기 때문에 다른 경우로 넘긴다.

3. 느낀점

이번 문제는 분명 구현이었는데 내 생각에는 구현보다는 백트래킹 혹은 브루트 포스를 활용할 줄 알고 약수를 구할 때 효율적으로 구할 수 있다면 아무런 문제 없이 해결할 수 있을 것이다.

최근에 이런 백트래킹 문제를 안풀어본지 오래되서 기억이 잘 안났지만 그래도 잘 풀려서 다행이다.