[프로그래머스 - Python] 154538 - 숫자 변환하기

0.  문제 링크

 

 

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

프로그래머스

---

1.  풀이 방법

 

 

1. DP를 이용해서 문제를 풀었다.
2. 조금 더 최적화를 하기 위해서 for loop의 범위에도 제한을 주었고, 아래의 조건에도 제한을 주었다.
3. BFS로 풀까 잠시 고민했는데, x = 1이고, y = 1,000,000이고, n = 1일 경우에 제일 빠른 경우는 19번이다.
4. 첫 번째 단계에서 3개, 두 번째 단계에서 3^2개.... 19번째 단계에서는 3^19개.. 가 생성된다.....
5. 그래서 BFS는 절대 아닐거라고 판단하고, DP로 풀었다.

---

2.  코드

def solution(x, y, n):
    dp = [float('inf')] * (y + 1)
    dp[x] = 0
    
    for i in range(x, max(y - n, y // 3) + 1):      # 범위에 제한을 줌
        # 인덱스를 벗어나지 않으면 최솟값을 구함
        if i + n <= y:
            dp[i + n] = min(dp[i + n], dp[i] + 1)
        if i * 2 <= y:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
            if i * 3 <= y:
                dp[i * 3] = min(dp[i * 3], dp[i] + 1)
        # 인덱스를 벗어나면 continue함
    
    return -1 if dp[y] == float('inf') else dp[y]

---

3.  마무리