ACM 136, Ugly Numbers

http://acm.uva.es/p/v1/136.html

 

소수(prime factor)인 2, 3, 5의 승을 구하여 작은 순대로 정렬된 숫자들의 1500번째 값을 구해야 한다.

 

알고리즘을 찾아내 실시간으로 해결해보려고 했으나, introduce to algorithm에서 소인수에 대한 판정 자체도 쉽지 않다는 생각을 듣고 포기...: 그거 찾아내려고 3일동안 코드를 세번 짰는데... 안타깝다...

 

그 알고리즘을 포기하니 오히려 답은 쉽게 보였다. 나는 휴리스틱 스타일로 문제를 해결했다.

 

어느 큰 값 n을 구한다.

n 보다 작은 2의 제곱에 대한 숫자들을 구한다. 1, 2 , 4, 8, 16 ... < n

n 보다 작은 3의 제곱에 대한 숫자들을 구한다. 1, 3 , 6, 9, 27 ... < n

n 보다 작은 3의 제곱에 대한 숫자들을 구한다. 1, 5 , 25, 75 ... < n

 

이제 각 숫자들을 모두 곱하고, 구하는 수 n보다 큰 값은 버리면 된다. 구한 수열은 미정렬 상태이므로, 정렬해서 구하려는 x 번째 값을 확인하면 된다. 만일 구한 수의 개수가 x보다 작으면 n을 더욱 크게 하면 된다.

 

그런데... 큰 값을 세 개씩 곱하면 오버플로가 날 거라는 생각을 미처 못하고 미련하게 곱하다가 버려져야할 수들이 구해진 수열에 끼어버렸다. 덕분에 오류를 찾는데 2시간이나 걸렸다... 이번에도 불만족. 다음에는 오버플로에 대한 catch를 확실히 하든지, 아니면 차라리 unsigned를 두지 않고 0보다 작은 값을 체크하는 것이 나을 것 같다는 생각이 든다.

1135657657_Ugly Numbers.cpp

1135658452_calc.cpp

n번째 ugly number를 구한다. 별다른 연산이 없어 빠르게 결과를 확인할 수 있다.