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

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

풀이

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

using namespace std;

void calculate(int num, int y,int n ,set<int>& hash, queue<int>& q){
    if(num + n <= y && hash.count(num + n) == 0){
        hash.insert(num+n);
        q.push(num+n);
    }
    if(num * 2 <= y && hash.count(num * 2) == 0){
        hash.insert(num * 2);
        q.push(num * 2);
    }
    if(num * 3 <= y && hash.count(num * 3) == 0){
        hash.insert(num * 3);
        q.push(num * 3);
    }
    return;
}

int solution(int x, int y, int n) {
    int answer = 0;
    queue<int> q;
    set<int> hash;
    q.push(x);
    while(!q.empty()){
        int len = q.size();
        for(int i = 0; i < len; i++){
            if(q.front() == y){
                return answer;
            }
            int nx = q.front();
            q.pop();
            calculate(nx, y, n, hash, q);
        }
        answer++;
    }
    return -1;
}

 

다른 풀이2

#include <string>
#include <vector>

using namespace std;
int dp[1000001];
int solution(int x, int y, int n) {
    int answer = 0;
    fill(dp, dp + 1000001, INT16_MAX);
    dp[x] = 0;
    for(int i = x; i <= y; i++){
        if(i + n <= y){
            dp[i+n] = min(dp[i+n], dp[i] + 1);
        }
        if( i * 2 <= y){
            dp[i * 2] = min(dp[i*2], dp[i] + 1);
        }
        if(i * 3 <= y){
            dp[i * 3] = min(dp[i*3], dp[i] + 1);
        }
    }
    answer = dp[y];
    if(answer == INT16_MAX){
        answer = -1;
    }
    return answer;
}

 

다른 풀이3

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

int bfs(int x, int y, int n){
    if(x == y){
        return 0;
    }
    vector<bool> check(y+1, false);
    queue<int> q;
    q.push(x);
    int depth = 1;
    while(!q.empty()){
        int len = q.size();
        for(int i = 0; i < len; i++){
            int now = q.front();
            q.pop();
            check[now] = true;
            int plus = now + n;
            int x2 = now * 2;
            int x3 = now * 3;
            if(plus == y || x2 == y || x3 == y){
                return depth;
            }
            if(plus < y && !check[plus]){
                q.push(plus);
            }
            if(x2 < y && !check[x2]){
                q.push(x2);
            }
            if(x3 < y && !check[x3]){
                q.push(x3);
            }
        }
        depth++;
    }
    return -1;
}
int solution(int x, int y, int n) {
    int answer = 0;
    answer = bfs(x, y, n);
    return answer;
}

 

다른 풀이4

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

using namespace std;

int solution(int x, int y, int n) {

    queue<pair<int, int>> q;
    q.push(make_pair(y, 0));
    
    while(!q.empty()){
        int val = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(val == x){
            return cnt;
        }
        if(val % 2 == 0){
            q.push(make_pair(val / 2 , cnt + 1));
        }
        if(val % 3 == 0){
            q.push(make_pair(val / 3, cnt + 1));
        }
        if(val - n > 0){
            q.push(make_pair(val - n, cnt + 1));
        }
    }
    
    return -1;
}