프로그래머스 숫자 변환하기 JavaScript
2023년 1월 29일
문제 풀이
다이나믹 프로그램밍을 이용해 y에서 x를 향해 숫자를 나누거나 빼주는 방식으로 푼 문제
문제에서 사용할 수 있는 연산은 +n, *2, *3이다. 이 코드에서는 y부터 숫자를 줄여가는 식으로 풀었기에, -n, /2, /3을 이용한다.
y부터 시작한 값 num이 num%2===0 num%3===0 num-n>0 인 조건을 만족하면서 이전에 방문했던 값인지 확인한다. 이전에 방문했으면 현재의 값보다 작은 값이기에 탐색하지 않는다. 조건에 맞으면 배열 dp를 갱신한다.dp[연산된 인덱스] = dp[num] + 1
solution.js
function solution(x, y, n) {
const dp = new Array(y+1).fill(-1);
dp[y] = 0;
const que = [y];
while (que.length > 0) {
const num = que.shift();
if(num === x) {
break;
}
if (num % 2 === 0 && dp[num/2] === -1) {
que.push(num/2);
dp[num/2] = dp[num]+1;
}
if (num % 3 === 0 && dp[num/3] === -1) {
que.push(num/3);
dp[num/3] = dp[num]+1;
}
if (num - n > 0 && dp[num-n] === -1) {
que.push(num-n);
dp[num-n] = dp[num]+1;
}
}
return dp[x];
}