[프로그래머스]level.2 - 숫자 변환하기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

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

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

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

내 풀이

첫번째 풀이

dfs

#include <string>
#include <vector>

using namespace std;
int Answer = -1;

void dfs(int x, int y, int n, int count)
{
    if(x == y)
    {
        if(Answer == -1 || Answer > count)
            Answer = count;
        return;
    }
    else if(x > y)
        return;
    
    dfs(x+n, y, n, count+1);
    dfs(x*2, y, n, count+1);
    dfs(x*3, y, n, count+1);
}

int solution(int x, int y, int n) {
    dfs(x, y, n, 0);
    return Answer;
}

시간초과,,,

 

두번째 풀이

dp

목표 숫자 Y 부터 시작 숫자 X까지 이동하면서 최소 이동 횟수를 구한다.

#include <string>
#include <vector>
#include <memory.h>

using namespace std;

int solution(int x, int y, int n) {
    int dp[1'000'001];
    memset(dp, 1'000'001, 1'000'001 * sizeof(int));
    
    dp[y] = 0;
    for(int i = y; i > x; --i)
    {
        if(i-n > 0)
            dp[i-n] = min(dp[i-n], dp[i]+1); 
    
        if(i%2 == 0)
            dp[i/2] = min(dp[i/2], dp[i]+1);
        
        if(i%3 == 0)
            dp[i/3] = min(dp[i/3], dp[i]+1);
    }
    
    if(dp[x] >= 1'000'001)
        dp[x] = -1;
    
    return dp[x];
}