문제설명

자연수 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://programmers.co.kr/learn/challenges

설계 과정

• DFS 활용
  dfs(x,count) -> x => 더해지는 값 , count=> 몇번 계산이 이어졌는지

1. x값이 y랑 같아지면 리턴
   -> 단, count값을 기존 최솟값과 비교해서 더 작다면 최소값 재할당
2. x>y 라면 그냥 리턴 => 값이 넘어갔기 때문에 계산할 필요가 없음.
3. 두개 다 아니라면 DFS반복 (3개)
4. dfs(x2,count+1)
   2.dfs(x3,count+1)
   3.dfs(x+n,count+1)

초기 코드

function solution(x, y, n) {
    var answer = -1;
    var count = 0;
    function dfs(x,count){
        if(x===y){
            //초기값 잡기
            if(answer===-1){
                answer = count;
            }
            else{
                if(answer>count) answer = count;
            }
            return;
        }
        else if(x>y) return;
        else{
            dfs(x*2,count+1)
            dfs(x*3,count+1)
            dfs(x+n,count+1)
        }
    }
    
    dfs(x,count);    
    return answer;
}

결과

우선 결과는 무조건 나온다. 단, 시간초과가 나온다. 보통 DFS나 BFS로 풀다가 시간 초과가 나오면 DP를 도전해본다.

개선 설계

dpArr을 y+1개 만큼 생성하고 -1로 채움.
그 후에 dpArr[x] = 0이라고 초기값 설정

• 이제 x~y까지 차례대로 아래 과정 계산 -> i라고 가정

1. dpArr[i] === -1 => 패스 (나올 수 없는 수임)
2. i + n < y -> n을 더할 수 있는 i라면?
   -> dpArr[i+n]이 처음 도달한 값이라면 그전꺼에 +1해서 할당
   -> 처음 도달한게 아니라 값이 존재한다면 작은걸로 설정
3. i 2 , i 3도 이 방법을 똑같이 진행

• 마지막에 dpArr[y]를 리턴

개선 코드

function solution(x, y, n) {
    var dpArr = new Array(y+1).fill(-1);
    dpArr[x] = 0;

    for(var i = x;i<=y;i++){

        if(dpArr[i]===-1){
            continue;
        }

        if(i+n<=y){
            if(dpArr[i+n]===-1){
                dpArr[i+n] = dpArr[i]+1;
            }
            else{
                dpArr[i+n] = dpArr[i+n]>dpArr[i]+1?dpArr[i]+1:dpArr[i+n];
            }
        }
        if(i*2<=y){
            if(dpArr[i*2]===-1){
                dpArr[i*2] = dpArr[i]+1;
            }
            else{
                dpArr[i*2] = dpArr[i*2]>dpArr[i]+1?dpArr[i]+1:dpArr[i*2];
            }
        }
        if(i*3<=y){
            if(dpArr[i*3]===-1){
                dpArr[i*3] = dpArr[i]+1;
            }
            else{
                dpArr[i*3] = dpArr[i*3]>dpArr[i]+1?dpArr[i]+1:dpArr[i*3];
            }
        }
    }
    return dpArr[y];
}

결과

만약 본인과 같이 dfs를 풀다가 시간초과가 난다면 불필요한 과정을 줄일 수 있는 DP 를 이용해보자.