[이코테] 다이나믹 프로그래밍 - 못생긴 수

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라. 예를 들어 11번째 못생긴 수는 10이다.

입력조건

• 첫째 줄에 n이 입력된다.(1 <= n <= 1,000)

출력조건

• n번째 못생긴 수를 출력한다.

사고과정

• 다이나믹 프로그래밍으로 푼다고 풀었는데.. 엄청 효율적인 코드는 아닌 듯 했다 느낌상..? 우선 주어진 데이터 범위가 적기 때문에 내 코드도 통과할 것 같긴 했다..
• 풀이를 보니 또(?) 참신한 풀이를 배울 수 있었다. n이 증가하면서 2, 3, 5의 배수를 기록해주면 되었다. 풀이에서 제공하는 코드를 눈으로만 이해하기 어려웠다.. 연습장에 코드를 일일이 써가면서 이해했다. 개인적으로 선언하는 변수가 많아서 헷갈렸다.. 핵심은 2, 3, 5의 배수 인덱스를 별도로 설정해서 n이 증가함에 따라 DP 테이블을 갱신하면 되었다(아마 코드로 이해하는 게 편할 듯 하다..)
• 참고로 아래 책 풀이의 elif 로 하면 틀리게 된다. 왜냐하면 2,3,5의 최소 공배수 값들이 elif로 하면 중복해서 들어가기 때문이다! 그러므로 if를 넣어주어 최소 공배수 값들이 하나만 들어가도록 설정하자!

풀이

1. 책 풀이(권장)

n = int(input())
ugly = [0] * n
ugly[0] = 1

# 2,3,5의 배수의 각 인덱스
i2 = i3 = i5 = 0
next2, next3, next5 = 2, 3, 5

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

print(ugly[n-1])

2. 스스로 푼 풀이

n = int(input())
dp = [False] * (1001)
dp[1] = True

for i in range(2, 1001):
    if i % 2 == 0:
        dp[i] = True
    elif i % 3 == 0:
        dp[i] = True
    elif i % 5 == 0:
        dp[i] = True

result = [i for i in range(len(dp)) if dp[i] is True]
print(result[n-1])