[Lv 2] 숫자 변환하기

 

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

프로그래머스

 

이 문제는 DP를 사용해 해결할 수 있다.

숫자 x를 y로 만드는 방법은 3가지가 있다.

1. n을 x에 더하기

2. x에 2를 곱하기

3. x에 3을 곱하기

 

위 방식을 생각해 본다면 y에서 x로 1씩 감소시키면서 반복을 진행할 때 1씩 감소시킨 값이 3이나 2로 나누어 떨어지거나 n과 뺐을 때 0보다 큰 경우 계속해서 연산할 수 있다는 것을 알 수 있다.

따라서 연산이 가능할 때 연산 횟수가 최소인 경우를 구하면된다.

즉, DP 배열에 연산이 가능할 때 연산 횟수를 누적하고 누적한 값을 최소로 만든다.

반복이 끝났을 때 DP[x]에는 최소 연산 횟수가 남아 있을 것이고, 배열을 초기화 한 값으로 남아 있다면 -1을 반환한다.

 

#include <string>
#include <vector>

using namespace std;

int dp[1000001] = {0,};

int solution(int x, int y, int n) {
    int answer = 0;
    for(int i = 0;i<=1000001;i++)
        dp[i] = 1000001;
    
    dp[y] = 0;
    
    for(int i = y;i>x;i--){
        
        if(dp[i] != 1000001){
            if(i%3 ==0)
                dp[i/3] = min(dp[i/3], dp[i] + 1);
            
            if(i % 2 == 0)
                dp[i/2] = min(dp[i/2], dp[i] + 1);
            
            if(i - n > 0)
                dp[i - n] = min(dp[i-n], dp[i] + 1);
        }
    }
    if(dp[x] == 1000001)
        dp[x] = -1;
    answer = dp[x];
    return answer;
}