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

문제 출처

숫자 변환하기

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

테스트 케이스

10 40 5
answer: 2
10 40 30
answer: 1
2 5 4
anser: -1

알고리즘 분류

DP

풀이

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

using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    int DP[1000001] = { 0 };
    for (int i = 1; i < 1000001; i++)
        DP[i] = 1000001;
    DP[y] = 0;
    for(int i = y; i > x; i--)
    {
        if (DP[i] != 1000001)
        {
            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] == 1000001)
        DP[x] = -1;
    answer = DP[x];
    return answer;
}

DP라는 배열을 선언해 주고 1000001으로 초기화해 줍니다.(x, y의 최댓값이 1000000) DP[y]를 0으로 바꾸어 줍니다.(y에서 출발, y -> x) y부터 1까지 DP[i]가 1000001이 아닐 때 3으로 나눈 경우, 2로 나눈 경우, n을 뺀 경우 위 세 가지를 모두 실행해 DP 배열을 기존 값과 DP[i] + 1 중에서 작은 값으로 업데이트 해줍니다. DP[x]의 값에 변화가 없다면 -1을 반환해주고 그 외의 경우 DP[x]를 반환해 줍니다.