문제 154538. 숫자 변환하기

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

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

입력

• 자연수 x, y, n

입력 제한

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입력 예제

// input
19 40 5 // x, y, z

// ans
2

 

풀이 방식

"최소 횟수로 결과에 도달하라"라는 문제는 다양한 유형의 문제가 있지만 해당 문제는 이전에 방문한 곳을 다시 방문해서는 안되는 유형이므로 BFS가 적절하다. BFS는 미로에서 최소 이동 횟수로 도착 지점에 도달하는 문제의 대표적인 풀이 방식이기 때문. 이 문제도 x라는 출발지에서 y라는 도착지에 도달하는 것이니 미로와 다를 바가 없다. 

따라서 미로를 풀 듯 BFS를 똑같이 적용하여 해당 문제를 풀면 된다. BFS에 대한 설명과 구현방식은 따로 설명하지 않겠다.

 

정답 코드 

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

#define MAXN 1'000'000

using namespace std;

int X, Y, N;

bool inRange(int x){
    return 0 < x && x <= MAXN;
}

int bfs(){
    int ans = 0;
    
    if(X == Y) return 0;
    
    vector<bool> visited(MAXN+1);
    queue<int> q;
    
    visited[X] = true;
    q.push(X);
    
    while(!q.empty()){
        int q_size = q.size();
        ans++;
        
        for(int i = 0; i < q_size; i++){
            int cur_pos = q.front(); q.pop();
            vector<int> next = {cur_pos + N, cur_pos*2, cur_pos*3};

            for(int elem : next){
                if(elem == Y) return ans;

                if(inRange(elem) && !visited[elem]){
                    visited[elem] = true;
                    q.push(elem);
                }
            }
            
        }
        
        
        
        
    }
    
    
    return -1;
}
int solution(int x, int y, int n) {
    X = x;
    Y = y;
    N = n;
    int answer = bfs();
    return answer;
}