C++ / 프로그래머스 / 숫자 변환하기

문제

 

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

프로그래머스

 

 

문제풀이

 

DP를 이용해 풀었다.

1부터 y까지 사용할 것이기 때문에 y + 1의 크기만큼 벡터를 선언한다.

x를 y까지 1씩 더하면서 반복문을 돌린다.

 

DP [x + n]이 DP [x] + 1보다 크다면 DP [x + n] = DP [x] + 1이 된다.

x에서 n을 더하면 x + n이 되므로 x칸 도달 횟수에 +1을 한 값이 DP [x + n] 이 된다.

x는 x부터 y까지이므로 INF를 제외하고 해당 벡터에 값이 있다면 그 값은 최솟값이 된다.

 

x * 2, x * 3도 위와 마찬가지로 작성하면 된다.

 

코드

#include <string>
#include <vector>
#define INF 1e6
using namespace std;


int solution(int x, int y, int n) {
    vector<int>DP(y + 1, INF);

    DP[x] = 0;
    for (x; x <= y; ++x) {
        if (x + n <= y && DP[x + n] > DP[x] + 1)
            DP[x + n] = DP[x] + 1;

        if (x * 2 <= y && DP[x * 2] > DP[x] + 1)
            DP[x * 2] = DP[x] + 1;

        if (x * 3 <= y && DP[x * 3] > DP[x] + 1)
            DP[x * 3] = DP[x] + 1;

        if (DP[y] != INF) return DP[y];
    }

    return -1;
}