[2025.03.11] 숫자 변환하기

문제 설명

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

 

 

입출력 예

x			y	n	result	설명
10			40	5	2	x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.
10			40	30	1	x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.
2			5	4	-1	x를 y로 변환할 수 없기 때문에 -1을 return 합니다.
5			5	3	0	x와 y가 같으므로 연산할 필요가 없어 0을 return합니다.

 

 

문제 풀이

풀이 언어 : C++

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

using namespace std;

vector<vector<int>> graph;

int solution(int x, int y, int n) {
    int answer = 0;
    queue<pair<int, int>> q;
    unordered_set<int> visited;
    
    // root 설정
    q.push({x, 0});
    visited.insert(x);
    
    while(!q.empty())
    {
        // 현재 방문중인 노드
        int current=q.front().first;
        int depth=q.front().second;
        q.pop();
        
        // 현재 노드가 y일 때
        if(current==y) return depth;
        
        // 새로운 노드들
        int next1=current+n;
        int next2=current*2;
        int next3=current*3;
        
        // y보다 작거나 같고 visited에 존재하지 않다면 노드 추가
        if(next1<=y&&visited.find(next1)==visited.end())
        {
            q.push({next1, depth+1});
            visited.insert(next1);
        }
        
        if(next2<=y&&visited.find(next2)==visited.end())
        {
            q.push({next2, depth+1});
            visited.insert(next2);
        }
        
        if(next3<=y&&visited.find(next3)==visited.end())
        {
            q.push({next3, depth+1});
            visited.insert(next3);
        }   
    }
    return -1; // 변환할 방법이 없을 때
}

코드 설명

 

참고 사항

참고 사항 내용

 

 

오답 노트

문제를 풀 전체적인 방향성은 생각해봤지만 BFS라는 방법을 사용할 줄 몰라서 거의 찾아보면서 풀었다고 해야할 듯하다.

 

 

문제 링크

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

프로그래머스