[Programmers]#Level2_숫자 변환하기, DP

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

동적 계획법은 주어진 입력 크기에 따라 하위 문제들을 재귀적으로 해결하고, 그 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 일반적으로, Top-Down 혹은 Bottom-Up 방식으로 점화식을 세워 코드를 작성합니다. DFS와 트리 자료구조에서 주로 활용됩니다.

 

2. Top-Down 방식의 점화식 세워 DP를 구현

1. DFS를 활용할 경우, 시간 초과가 발생. 자연스럽게, DFS -> DP로 선회하여, y부터 x로 가는 Top-Down 방식의 점화식을 세워 DP를 구현합니다.
2. y -> x 순서로 DP를 수행하며 총 3가지 경우에 대하여 경우의 수를 구하고, 이중 최소가 되는 값을 Memoization 합니다. 마지막으로, dp [x] 값이 업데이트되었다면, 그 값을 결과 값으로 반환합니다.

 

---

 

#3. 코드

/*
    @문제 : 주어진 x를 3가지 방법(x*3, x*2, x+n)을 최소한으로 활용하여 Y를 만드는 연산 횟수
    @설명
        1. dfs 활용 시 시간 초과 발생
        2. dp 활용, y부터 x까지 역순으로 DP수행하여 dp[x]를 반환
*/

#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

#define MAX 1000001

int ans = INT_MAX;
vector<int> op = {2, 3};
vector<int> dp(MAX, INT_MAX);

int solution(int x, int y, int n)
{
    dp[y] = 0;

    for (int i = y; i > x; --i)
    {
        if (dp[i] != INT_MAX)
        {
            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] == INT_MAX)
        return -1;
    else
        return dp[x];
}

 

---