[C++] 숫자 변환하기

[문제]

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

bfs를 이용해서 접근을 하자.

또한 시간절약을 위해서 x부터 y로 가지 말고 y부터 x로 다가가자. ( x부터 y로 갈경우 매번 3^n의 경우가 생기지만 y에서 x로 갈경우 %3이나 %2가 안되는 경우 1개의 가지만 생기기에 경우가 적어진다.)

그렇게 접근을 해서 만약 x가 나온다면 반복문을 종료, x보다 적어진다면 continue를 해주자.

[회고]

처음에 dfs를 이용해서 접근을 했다가 시간초과가 났었다.

n의 크기가 유동적이기에 언제는 n이 1, x도 1, y가 1,000,000 이라면 경우의 수가 너무 많이 생기고 그렇다고 n을 빼주는 경우를 유동적으로 접근할 수 있는 방법이 생각나지 않아서 dfs가 아니라 bfs를 사용하기로 했다.

[코드]

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int min_ans = 999999;

void bfs(int x, int y, int n){
    queue<pair<int, int> > q;
    q.push(make_pair(y,0));
    
    while(q.size() > 0){
        int cur = q.front().first;
        int curNum = q.front().second;
        q.pop();
        if(cur == x){
            min_ans = curNum;
            break;
        }
        else if(cur < x){
            continue;
        }
        if(cur % 3 == 0){
            q.push(make_pair(cur / 3, curNum + 1));
        }
        if(cur % 2 ==0){
            q.push(make_pair(cur / 2, curNum + 1));
        }
        q.push(make_pair(cur - n, curNum + 1));
    }
    return;
}

int solution(int x, int y, int n) {
    int answer = 0;
    bfs(x,y,n);
    
    answer = (min_ans == 999999) ? -1 : min_ans;    
    return answer;
}