ALGOSPOT - WEIRD

문제

https://algospot.com/judge/problem/read/WEIRD

풀이

알고스팟 튜토리얼에 있는 문제. 얼마전까지만해도 이 문제 풀지도 못했는데 지금은 풀 수 있는걸 보면 0.1% 정도는 실력이 늘은것같다.

어떤 수 N이 주어질때 그 수가 Weird한 수인지 판별하는 문제인데, Weird 여부를 판별하려면 아래 두 조건 중 하나라도 만족해야한다.

• N의 진약수들 중 일부의 합으로 N을 만들수 없다.

• 모든 진약수들의 합이 N보다 크다.(greater than N)

문제에는 Weird하지 않은 수의 조건이 나와있고 위의 조건은 Weird한 수의 조건이므로 혼동하지 말기를 바란다.

서너번 정도 제출하는데 계속 WA가 나와서 코드를 다시 훑어보았더니 두번째 조건을 빼먹었다. 댓글을 보니까 나와 같은 사람이 한둘이 아니더라..

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int solve(vector<int> &v,int sum, int depth){
	if(sum == n)return 1;
	if(sum > n || depth<0) return 0;
	return solve(v,sum+v[depth],depth-1) || solve(v,sum,depth-1);
}
int main() {
	int t,i,sum,flag,divsum;
	vector<int> pd;
	scanf("%d",&t);
	while(t--){
		divsum=sum=0;
		pd.clear();
		scanf("%d",&n);
		for(i=1;i<n;i++){
			if(n%i==0){
				pd.push_back(i);
				divsum+=i;
			}
		}
		sort(pd.begin(),pd.end());
		puts(divsum <= n || solve(pd,0,pd.size()-1)?"not weird":"weird");
	}
	return 0;
}