programmers 숫자 변환하기

programmers

level2 숫자 변환하기

문제설명

위의 이미지를 클릭하면 해당 문제로 이동합니다.

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

using namespace std;

int solution(int x, int y, int n) {
    int answer = -1;
    queue<pair<int, int>> bfs;
    if(x == y) return 0;
    bfs.push({x,0});
    vector<int> record(1000000, 0);

    while(bfs.size()!=0){
        int cur = bfs.front().first;
        int cnt = bfs.front().second;
        vector<int> temp = {cur*2, cur*3, cur+n};
        for(int i : temp){
            if(i == y ) return cnt+1;
            else if(i < y && record[i]==0){ bfs.push({i, cnt+1}); record[i]=1;}
        }
        bfs.pop();
    }

    return answer;
}

해결과정

queue를 이용하여 bfs로 가능한 경우를 탐색하며 해결하였다. 첫번째 시도에서는 3개의 실패를 했는 데, 하나는 아무 연산을 하지 않고도 x와 y가 같은 경우를 고려하지 못했고, 나머지 두 개는 시간 초과였다. if문으로 연산하기 전에 x와 y를 비교해주었고, vector를 선언하여 이전에 queue에 추가해주었던 수라면 다시 추가하지 않도록 해주었다. 이를 통해 모든 실패를 해결할 수 있었다. 자꾸 일단 시도해보고 고치려고 하는 데, 위와 같은 잘못은 미리 찾아내어 해결하는 연습을 더 해야겠다.