접근 ¶
처음 문제를 제대로 이해하지 않고 '그냥 2,3,5 외의 소수 제외한것 아닌가?' 로 접근하다가 14 는 아니라는 것을 간과. 다시 처음부터 접근.
연습장에 이것저것 써보다가 대략 두가지 접근법이 생각나다. 하나는 각 수들마다 'isUglyNumber' , 하나는 지수를 이용한 방법. 일단은 'isUglyNumber' 먼저 구현해보기로 해봄. (워낙 간단하므로)
~cpp
def isDivideOnly235(number):
while True:
if number == 1: return True
if number % 2 != 0 and number % 3 !=0 and number % 5 != 0: return False
number = toDivide(number)
def toDivide(number):
for x in [2,3,5]:
if number % x == 0: number=number/x
return number
def uglyNumber(count):
if count == 1: return 1
idx = 2
currentCount = 2
while True:
if isDivideOnly235(idx):
print idx,currentCount
if currentCount == count:
return idx
currentCount += 1
idx+=1
하지만, 결과값을 보면서 지수 스타일의 접근법이 원하는 접근법이라는 생각을 하게 되다. (10억이 넘는다 할때, isUglyNumber 식이라면 10억번이 실행된다.) 하지만, 그냥 지수로만 생각하면 uglynumber 의 순서 상 맞지 않을 것인지라 (1 : 2^0*3^0*5^0, 2 : 2^1*3^0*5^0, 3 : 2^0*3^1*5^0, 4 : 2^2*3^0*5^0 ... 0,0,0 , 1,0,0, 0,1,0 , 2,0,0 .. 도무지 숫자들 간의 연관성이 잡히지 않았다.
그러다가, '에이.. 걍 sort 해버리자.' 접근. 하지만, n 값에 따라 결과가 영향을 받을 것이라는 막연한 생각에 연습장에서 한참 고민. 그냥 실제 원하는 값 보다 여유분 값을 만들고 적당히 답을 내는 방식으로 접근. 하지만, 무언가 굉장히 찝찝함.
UglyNumbers/JuNe 코드 분석. 2시간 동안 보다가 도무지 접근법을 이해 못하다. 한 3시간째쯤 보다가 http://www.acmsolver.org/?itemid=28#ggviewer-offsite-nav-9512048 보고 이해 & 좌절.
나중에 어떤 생각을 하면 저 방법이 떠오를까에 대해 고민.
--1002
나중에 어떤 생각을 하면 저 방법이 떠오를까에 대해 고민.
--1002
- 동감. DamienRice 20080929
