[프로그래머스] 숫자 변환하기 (C++)

숫자 변환하기 / Lv.2

---

문제  설명 )

자연수 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

 

 

입출력 예 )

 

 

입출력 예 설명 )

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

 

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

 

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

 

 

풀이)

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int visited[1000001];
 
int _y, _n;
 
int bfs(int x)
{
    queue<int> q;
    visited[x] = 1;
    q.push(x);
    
    while(!q.empty())
    {
        int a = q.front();
        q.pop();
        
        if(a == _y)
        {
            return visited[a] - 1;
        }
        
        int nx = a + _n;
        if(!visited[nx] && nx <= 1000000)
        {
            visited[nx] = visited[a] + 1;
            q.push(nx);
        }
        
        nx = a * 2;
        if(!visited[nx] && nx <= 1000000)
        {
            visited[nx] = visited[a] + 1;
            q.push(nx);
        }
        
        nx = a * 3;
        if(!visited[nx] && nx <= 1000000)
        {
            visited[nx] = visited[a] + 1;
            q.push(nx);
        }
    }
    
    return -1;
}
 
 
int solution(int x, int y, int n) {
    _n = n;
    _y = y;
    
    return bfs(x);
}

---

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

프로그래머스