U E D R , A S I H C RSS

Ugly Numbers/1002

접근

처음 문제를 제대로 이해하지 않고 '그냥 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

- 동감. DamienRice 20080929
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0495 sec