[C++/PGS] Lv.2 : 숫자 변환하기

 

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

프로그래머스

---

프로그래머스 레벨 2

dfs로도 쉽게 풀 수 있지만, 효율성 때문에 dp로 해결해야 하는 문제이다.

이전 값으로부터 현재값으로 계산이 가능한 값인지 확인 후, 연산해야 한다.

 

나의 풀이

#include <string>
#include <vector>
#include <climits>
using namespace std;

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