[홀로 하는 코딩 공부] 숫자 변환하기(Python)

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

 

*** 본 문제를 푸는 과정을 공유하려 한다.

 

---

▶ 처음에 본 문제를 보고 3가지 조건에 대해서 dfs 방법으로 풀이 방향을 정했고, 아래와 같이 코드를 작성하였다.

def solution(x, y, n):
    answer = -1

    def dfs(src, cnt):
        nonlocal answer
        if src == y:
            if answer == -1:
                answer = cnt
            else:
                answer = min(answer, cnt)
            return
        else:
            if src+n <= y:
                dfs(src+n, cnt+1)
            if src * 2 <= y:
                dfs(src*2, cnt+1)
            if src * 3 <= y:
                dfs(src*3, cnt+1)
        return

    dfs(x, 0)

    return answer

 

 

 

▶ 런타임에러다. 아래 조건과 런타임에러가 발생한 것을 기반으로 dfs 때문인 것 같다. 

• 1 ≤ x ≤ y ≤ 1,000,000

▶ 그래서 dp 풀이로 방향을 변경했다.

def solution(x, y, n):
    dp = [-1 for _ in range(max(y + n, y * 2, y * 3) + 1)]
    dp[x] = 0

    for i in range(x, y):
        if dp[i] == -1:
            continue

        if dp[i * 2] != -1:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
        else:
            dp[i * 2] = dp[i] + 1

        if dp[i * 3] != -1:
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)
        else:
            dp[i * 3] = dp[i] + 1

        if dp[i + n] != -1:
            dp[i + n] = min(dp[i + n], dp[i] + 1)
        else:
            dp[i + n] = dp[i] + 1

    return dp[y]

 

 

 

 

▶ 성공이다!!

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.