[프로그래머스 Lv.2] 숫자 변환하기

[문제]

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

 

[풀이]

 

DP로 풀었다.

#include <string>
#include <vector>

using namespace std;

// 자연수 x를 y로 변환
// 1. x + n
// 2. x * 2
// 3. x * 3
// 위 세 가지 연산을 사용해서 최소 횟수로 y만들기
int solution(int x, int y, int n)
{
    vector<int> DP(y + 1, INT32_MAX);
    DP[x] = 0;

    for (int i = x; i <= y; i++)
    {
        if (DP[i] == INT32_MAX) continue;
        if ((i * 3) <= y) DP[i * 3] = min(DP[i * 3], DP[i] + 1);
        if ((i * 2) <= y) DP[i * 2] = min(DP[i * 2], DP[i] + 1);
        if ((i + n) <= y) DP[i + n] = min(DP[i + n], DP[i] + 1);
    }

    return DP[y] == INT32_MAX ? -1 : DP[y];
}