쉬운 문제로 나왔는데 은근히 어려웠던 Weird Numbers 였습니다. 프로그래밍 대회 공부를 하신 분들한테는 잘 알려진 문제일 것 같아서 별 부담 없이 냈는데, 자잘한 최적화 포인트가 여럿 있어서 이게 사람 잡더군요. ^^

이 문제의 포인트는 두 가지입니다.

1. 모든 proper divisor 찾기
2. proper divisor 로 해당 숫자를 만들 수 있는지 확인하기

proper divisor 를 구하는 것은 단순하죠. O(n) 에 됩니다:

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

n 이 어떤 수의 자승일 때 한 수가 중복으로 추가되는 걸 막기 위해서 if 문이 하나 더 들어간 것에 유념하시고요. 여튼 이런 최적화를 하면 채점 사이트 (일명 리베셋) 에서 3배쯤 빨라집니다. -_-;

그리고, 일단 divisor 를 다 더해봐서 n 을 넘지 않는다면 일단 절대 weird number 일 수 없죠.

그리고 나면, 해당 숫자를 만들 수 있는지 시도해 보아야 합니다. 이 문제는 사실 유명한 문제와 거의 비슷한데요, 바로 작년 인터넷 예선에도 나온 바 있는 0-1 배낭 문제입니다. 위키피디아 링크 참조하세요. ^^

간략하게 설명하자면, divisor 들을 일렬로 쭉 늘어놓고, 첫 i개의 숫자를 봅니다. 그러면, 2^i 개의 합이 있겠죠? (물론, 이 합들이 유니크하진 않을 수도 있지만, 논외로 하구요.) 이 때, 이 i개의 숫자 중 몇 개를 적절히 선택해 더해서 j 라는 숫자를 만들 수 있을까요?

이 함수를 canMake(i, j) 라고 합시다. 이 함수가 구현되어 있다면, weird() 함수의 나머지는 매우 간단하겠죠? canMake(divisors.size(), n) 을 호출하면 끝이니까요. 이 때, canMake 함수는 재귀적으로 다음과 같이 정의됩니다.


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() 는 좀 더 빠른 버전입니다. 
덧) 그리고.. weird 를 wierd, wired 로 쓰신 분들, 안타깝지만 다 No - Wrong Answer 드렸습니다. 이런거 주의하세요! ㅋㅋ
이 게시물을..