[프로그래머스] 숫자 변환하기 파이썬

https://school.programmers.co.kr/learn/courses/30/lessons/154538#qna

프로그래머스

문제를 보고, 처음에 그리디를 생각했는데 그리디 문제가 아니였다

그래서 dp를 생각하고 아래와 같이 풀었으나 75점을 받게 됐다.

#### 1차 풀이 => 75점 ####
def solution(x, y, n):
    answer = 0
    dp = [1000001]*(y+1)
    dp[x] = 0

    for i in range(x+1,y+1):
        if i % (x*6) == 0:
            dp[i] = min(dp[i//2], dp[i//3])+1
        elif i % (x*2) == 0:
            dp[i] = dp[i//2]+1       
        elif i % (x*3) == 0:
            dp[i] = dp[i//3]+1
        if i-n >= 0:
            dp[i] = min(dp[i], dp[i-n]+1)
   
    return dp[y] if dp[y] != 1000001 else -1

ㅎㅎ... 도저히 틀린 케이스를 찾을 수 없어서 다른 분들의 풀이를 참고하였다..

#### sol / 정답풀이
def solution(x, y, n):
    answer = 0
    memorize = [1e9] * (y+1)
    memorize[x] = 0
    for i in range (x, y+1):
        if i + n <= y:
            memorize[i+n] = min(memorize[i+n], memorize[i] + 1)
        if i * 2 <= y:
            memorize[i*2] = min(memorize[i*2], memorize[i] + 1)
        if i * 3 <= y:
            memorize[i*3] = min(memorize[i*3], memorize[i] + 1)
    
    if memorize[y] == 1e9:
        return -1
    return memorize[y]

이런 방법을 왜 생각 못 했을까.. dp 넘 어렵당

i번째에서 i+n, i*2, i*3 케이스를 모두 구해 해당 인덱스 위치에 넣어주는 것이다.

나는 i번째일 때, i번째 인덱스 값만 구했기 때문에 이 알고리즘이 훨씬 효율적인 것을 확인할 수 있었다.