프로그래머스 - 숫자 변환하기 [C++]

 이 문제는 다이나믹 프로그래밍을 이용해 풀었다. 사실 이 문제는 bfs로 풀어도 전혀 상관이 없어보이는게 2와 3을 곱해서 수가 빠른 속도로 커지기도 하고, x부터 시작해서 세 연산 모두 무조건 커지기 때문에 충분히 가능할 것 같다. 하지만 나는 이 문제를 처음 보자마자 dp가 떠올라서 그걸로 풀었다.

 

 

 다이나믹 프로그래밍으로 풀 때 유의 사항은 처음으로 dp 배열에 값을 집어넣는다고 해서 그 값이 최적이 아닐 수 있다는 사실이다. 처음에 나는 dp 배열이 -1이면 dp[i] + 1을 저장하고 다음 수로 넘어갔는데, 이렇게 하면 테스트 케이스에서 일부 오답이 나온다. 그래서 dp가 -1이 아니더라도 dp[i] + 1과 저장되어 있는 값을 비교하여 최소를 저장하는 로직을 집어넣었더니 바로 정답이 나왔다.

 

 

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

using namespace std;

int dp[1000001];

int solution(int x, int y, int n) {
    int answer = 0;
    
    // base case
    if (x == y) {
        return 0;
    }
    
    // init
    for (int i = 1; i <= 1000000; i++) {
        dp[i] = -1;
    }
    
    dp[x] = 0;
    
    for (int i = x; i <= y - 1; i++) {
        if (dp[i] != -1) {
            if (i + n <= y) {
                if (dp[i + n] == -1) {
                    dp[i + n] = dp[i] + 1;
                }
                else {
                    dp[i + n] = min(dp[i + n], dp[i] + 1);
                }
            }
            if (i * 2 <= y) {
                if (dp[i * 2] == -1) {
                    dp[i * 2] = dp[i] + 1;
                }
                else {
                    dp[i * 2] = min(dp[i * 2], dp[i] + 1);
                }
            }
            if (i * 3 <= y) {
                if (dp[i * 3] == -1) {
                    dp[i * 3] = dp[i] + 1;
                }
                else {
                    dp[i * 3] = min(dp[i * 3], dp[i] + 1);
                }
            }
        }
    }
    
    answer = dp[y];
    
    return answer;
}