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

문제

---

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

풀이

---

자연수 x를 y로 변환하기 위한 연산을 진행할 때, 최소 연산 횟수를 구하는 문제로, DP를 활용하여 연산에 따라 나올 수 있는 경우의 수를 계산한다. 먼저, fill로 dp 배열 값을 최대 값으로 정하고 주어진 연산이 더하기와 곱하기 밖에 없기 때문에 x와 y 사이 값을 비교하여 메모이제이션으로 채워나가 y에 도달하는 경우의 수를 찾고, min으로 최소 횟수를 저장한다.

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

using namespace std;

int dp[1000001];
int solution(int x, int y, int n) 
{
    int answer = 0;
    fill(dp, dp + 1000001, 10000000);
    dp[x] = 0;

    for (int i = x; i <= y; i++)
    {
        if (i + n <= y)
        {
            dp[i + n] = min(dp[i + n], dp[i] + 1);
                
        }

        if (i * 2 <= y)
        {
            dp[i * 2] = min(dp[i * 2], dp[i] + 1);

        }

        if (i * 3 <= y)
        {
            dp[i * 3] = min(dp[i * 3], dp[i] + 1);

        }
    }

    answer = dp[y];

    if (answer == 10000000)
    {
        answer = -1;
    }

        
    return answer;
}