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 ... < nn 보다 작은 3의 제곱에 대한 숫자들을 구한다. 1, 3 , 6, 9, 27 ... < nn 보다 작..
2005. 12. 27.