못생긴 수

 

 

유형 파악 및 구현

이 문제는 생각해내는게 좀 어려웠던 것 같다.

못생긴 수는 2, 3, 5의 조합들을 의미한다.

 

못생긴 수의 리스트를 보면

1, 2, 3, 2x2, 5, 2x3, 2x2x2, 3x3, 2x5  이런식으로 진행된다.

즉 초기 못생긴 수를 넣고 (2, 3, 5) 이미 들어간 못생긴 수에 2, 3, 5를 곱하는 방식으로 진행된다.

 

구현을 하기 위해서는

2 or 3 or 5가 다음에 곱해져야하는 리스트 인덱스를 담는 변수  -> i2, i3, i5

결과마다 가장 작은 것을 뽑아서 리스트에 넣기 전 결과를 표현하는 변수 -> next2, next3, next5가 필요하다.

 

코드

# 찾으려는 인덱스
n = int(input())

# 못생긴 수 초기화
ugly = [0]*(n+1)
# 첫번째 못생긴 수는 1
ugly[0] = 1

# 전체리스트에서 2 or 3 or 5를 곱해야하는 차례를 의미
i2 = i3 = i5 = 0
# 결과로 담을 변수 초기화
next2, next3, next5 = 2, 3, 5

for i in range(1, n):
    ugly[i] = min(next2, next3, next5)
    if ugly[i] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[i] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[i] == next5:
        i5 += 1
        next5 = ugly[i5] * 5
    print(i2, i3, i5)
    print(ugly)
    print(" ")