[이것이 코딩테스트다] #35. 못생긴 수

• 본 문제는 <이것이 코딩테스트다 with python (한빛미디어, 나동빈 저) > 에 수록되어 있습니다.

 

문제

 

풀이

일단 이 문제는 다이나믹 프로그래밍 챕터에 수록되어 있는 문제이다. 

다이나믹 프로그래밍을 할 때 가장 먼저 생각해야되고 결국 핵심적인게 점화식을 구해야되는건데 ... 나의 머리는 잘 돌아가지 않는다 흑...

 

제일 먼저 못생긴 수를 저장할 dp테이블을 만든다. 못생긴 수는 2, 3, 5만을 약수로 가져야하므로 dp 테이블 내에 있는 숫자들에 계속해서 2, 3, 5를 곱해야되는 아이디어를 가지고 시작했다. 그리고 작은 수부터 dp 테이블에 저장해야 되는데.. 이 부분이 너무 어려웠다 ㅠㅠ

 

그래서 해설의 도움을 약간 (?) 받은 풀이 .. 사실 두 번째 푸는건데도 아직도 제자리걸음이다 에흉흉 ㅠㅠ 

 

dp = [0] * 1001

n = int(input())

dp[1] = 1

i2, i3, i5 = 1, 1, 1
next2, next3, next5 = 2, 3, 5

for i in range(2, n+1):
    dp[i] = min(next2, next3, next5)

    if dp[i] == next2:
        i2 += 1
        next2 = dp[i2] * 2

    if dp[i] == next3:
        i3 += 1
        next3 = dp[i3] * 3

    if dp[i] == next5:
        i5 += 1
        next5 = dp[i5] * 5
        
print(dp[n])

 

이런 생각은 대체 어떻게 하면 나오는 걸까 ????????????????????

나는 몇 번 안 풀어봐서 잘 모르는거겠지................?..............