[프로그래머스] 숫자 변환하기 (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

---

🚨 접근 방법

DP로 풀어야 한다는 생각이 들었다. 그러나 마땅한 아이디어가 떠오르지 않았다.
로직을 그림으로 그렸을 때 BFS를 이용하면 구현할 수 있을 것 같았다.
맨 처음 입력받은 x를 queue에 넣고 다음 값이 될 수 있는 3x, 2x, x+n에 대하여 방문 가능하다면 계속 탐색하고 x==y일 때 방문 횟수를 출력하는 방법이다.

---

🚈 풀이

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    vector<int> visit_cnt(1000001,0);
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        if(cur==y){
            return visit_cnt[cur];
        }
        int next[3]={cur+n,cur*2,cur*3};
        for(int i=0;i<3;i++){
            if(y<next[i]||visit_cnt[next[i]]!=0){
                continue;
            }
            visit_cnt[next[i]]=visit_cnt[cur]+1;
            q.push(next[i]);
        }
    }
    return -1;
}