[프로그래머스] 숫자 변환하기- python[ DP ]

[level 2] 숫자 변환하기 - 154538

문제 링크

성능 요약

메모리: 31.9 MB, 시간: 150.22 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2023년 11월 1일 12:45:19

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

---

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

코딩테스트 연습 | 프로그래머스 스쿨

나의 풀이

dp로 접근해야 하는 것은 보자마자 알았다 다만 2번째 줄에 너무 메모리 낭비가 심하지 않은가 고민은 했으나 따로 에러난 생기지는 않았다.

다른 사람의 풀이를 봤는데 set을 사용하여 y와 같은 값이 생길 때 까지 반복하여 set에 값을 더해주는 코드가 있었는데 이 방식이 메모리적으로 이득이 클 것 같은 방식이었다.

def solution(x, y, n):
    dp = [ -1 for i in range(y*3+1)]
    dp[x] = 0
    for i in range(x,y):
        if dp[i] == -1:
            pass
        else:
            if dp[i+n] != -1:
                dp[i + n] = min(dp[i]+1,dp[i+n])
            else: dp[i+n] = dp[i]+1

            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

    return dp[y]