쉬운 문제로 나왔는데 은근히 어려웠던 Weird Numbers 였습니다. 프로그래밍 대회 공부를 하신 분들한테는 잘 알려진 문제일 것 같아서 별 부담 없이 냈는데, 자잘한 최적화 포인트가 여럿 있어서 이게 사람 잡더군요. ^^
이 문제의 포인트는 두 가지입니다.
1. 모든 proper divisor 찾기
2. proper divisor 로 해당 숫자를 만들 수 있는지 확인하기
proper divisor 를 구하는 것은 단순하죠. O(n) 에 됩니다:

vector divisors;
for(int i = 1; i < n; ++i) if(n % i == 0) divisors.push_back(i);

하지만 이것보다 더 잘 할 수 있습니다. 왜냐면, i 가 n 의 약수라면 n/i 도 n 의 약수이기 때문이죠. 따라서 O(n^0.5) 으로 다음과 같이 할 수 있습니다:

vector divisors;
        for(int i = 1; i*i <= n; ++i)
        {
                if(n % i == 0)
                {
                        divisors.push_back(i);
                        if(n / i != i)
                                divisors.push_back(n / i);
                }
        }

n 이 어떤 수의 자승일 때 한 수가 중복으로 추가되는 걸 막기 위해서 if 문이 하나 더 들어간 것에 유념하시고요. 여튼 이런 최적화를 하면 채점 사이트 (일명 리베셋) 에서 3배쯤 빨라집니다. -_-;
그리고, 일단 divisor 를 다 더해봐서 n 을 넘지 않는다면 일단 절대 weird number 일 수 없죠.
그리고 나면, 해당 숫자를 만들 수 있는지 시도해 보아야 합니다. 이 문제는 사실 유명한 문제와 거의 비슷한데요, 바로 작년 인터넷 예선에도 나온 바 있는 0-1 배낭 문제입니다. 위키피디아 링크 참조하세요. ^^
간략하게 설명하자면, divisor 들을 일렬로 쭉 늘어놓고, 첫 i개의 숫자를 봅니다. 그러면, 2^i 개의 합이 있겠죠? (물론, 이 합들이 유니크하진 않을 수도 있지만, 논외로 하구요.) 이 때, 이 i개의 숫자 중 몇 개를 적절히 선택해 더해서 j 라는 숫자를 만들 수 있을까요?
이 함수를 canMake(i, j) 라고 합시다. 이 함수가 구현되어 있다면, weird() 함수의 나머지는 매우 간단하겠죠? canMake(divisors.size(), n) 을 호출하면 끝이니까요. 이 때, canMake 함수는 재귀적으로 다음과 같이 정의됩니다.
[code]canMake(i, j) => (j == 0 or canMake(i-1, j) or canMake(i-1, j-divisors[i-1]))[/code]
a. j = 0 이라면, i개에서 한 개도 안 고르면 되니까 ok입니다. 
b. 만약 i개중에 마지막 숫자를 빼 놓고, 첫 i-1 개만으로도 j 를 만들 수 있다면 ok 입니다.
c. i개 중에 마지막 숫자를 사용한다고 보고, 나머지 i-1 개로 j-divisors[i-1] 을 만들 수 있다면 ok 입니다.
이 점화식을 구현하면 됩니다. canMake(i, j) 의 결과값을 a[i, j] 에 저장한다고 생각하고, 배열 a 를 계산하면 되죠. 그런데, 이렇게 하면 배열 a 의 크기는 (divisors.size() * n) 이 되기 때문에, 메모리 한계를 초과하게 됩니다. 
따라서 이거를 1차원으로 펴 줘야 하죠. 2차원 배열인 a의 한 줄만큼의 용량을 가지고, a의 마지막 줄을 계산해 내는 것입니다. 어떻게 할까요? 요건 독자분들을 위한 숙제로 남겨두겠습니다. :)
이 문제는 이 외에도 최적화할 포인트가 많습니다. 직접 짜신 코드와 아래 저지 답안을 비교해 보시면서 어떤 점이 다른지 살펴보세요. 만약 제가 생각 못한 최적화가 있다면 알려 주시고요.. ^^
다음은 소스코드입니다. weird() 는 좀 느린 버전, weird2() 는 좀 더 빠른 버전입니다. 
[code]
bool bitmask[1000001];
bool weird(int n)
{
vector divisors;
divisors.push_back(1);
for(int i = 2; i*i <= n; ++i)
{
if(n % i == 0)
{
divisors.push_back(i);
if(n / i != i)
divisors.push_back(n / i);
}
}
if(accumulate(divisors.begin(), divisors.end(), 0) <= n) return false;
memset(bitmask, 0, sizeof(bitmask);
bitmask[0] = true;
for(int i = 0; i < divisors.size(); ++i)
{
for(int j = n - divisors[i]; j >= 0; --j) if(bitmask[j])
if(j + divisors[i] <= n)
{
bitmask[j + divisors[i]] = true;
if(j + divisors[i] == n)
return false;
}
}
return true;
}
bool weird2(int n)
{
vector canMake;
vector divisors;
divisors.push_back(1);
for(int i = 2; i*i <= n; ++i)
{
if(n % i == 0)
{
divisors.push_back(i);
if(n / i != i)
divisors.push_back(n / i);
}
}
if(accumulate(divisors.begin(), divisors.end(), 0) <= n) return false;
memset(bitmask, 0, sizeof(bitmask);
canMake.clear();
canMake.reserve(n+10);
bitmask[0] = true;
canMake.push_back(0);
for(int i = 0; i < divisors.size(); ++i)
for(int j = canMake.size()-1; j >= 0; --j)
{
int k = canMake[j] + divisors[i];
if(!bitmask[k] && k <= n)
{
if(k == n) return false;
bitmask[k] = true;
canMake.push_back(k);
}
}
return true;
}
[/code]
덧) 그리고.. weird 를 wierd, wired 로 쓰신 분들, 안타깝지만 다 No - Wrong Answer 드렸습니다. 이런거 주의하세요! ㅋㅋ