[프로그래머스] 숫자 변환하기 Lv2

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=javascript

프로그래머스

 

자연수 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

 

이건 보자마자 무조건 dp 문제다라고 판단했다. dps로 풀 수도 있겠지만 이런 유형 문제는 보통 그럼 시간 초과가 났던 걸로 기억이 나서 급하게 dp를 공부해서 풀었다.

 

function solution(x, y, n) {
    const dp = new Array(y+1).fill(1000001);
    dp[x] = 0;
    for(let i=x; i<=y; i++){
        dp[i+n] = Math.min(dp[i+n],dp[i]+1);
        dp[i*2] = Math.min(dp[i*2],dp[i]+1);
        dp[i*3] = Math.min(dp[i*3],dp[i]+1);
    }
    return dp[y]!==1000001? dp[y] : -1;
}

 

혹시 몰라 풀이를 적자면 일단 y의 길이 +1 만큼을 가장 큰 수보다 1 큰 숫자로 채워 더 큰 숫자가 없게 세팅한다.

 

그리고 x부터 +n, x2, x3을 인덱스에 실시하고 최초 실행인 [dp[x] + 1] 즉, 1과 +n, x2, x3 실행한 위치를 min으로 비교한다.

 

Math.min(1000001, 1)이 될 것이다.

 

해당 내용을 반복하다보면 1이 된 인덱스에 i가 도착하게 될 것이고 1+1과 1000001을 비교하는 것이 반복되다 보면 ex) (n+1, 1000001)

 

y인덱스에서 최종값이 나오거나 1000001로 유지되게 된다.