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 2021-02-07 05:28:19
Processing time 0.0125 sec