[프로그래머스][C++][154538] 숫자 변환하기

[문제 출처]

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

1. 문제

설명

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

2. 설명

 처음에 모든경우의수를 dfs를 통해 구한후 제출하였더니 시간초과가 발생하였습니다.

그다음은 bfs로 제출했는데 또다시 시간초과가 발생하였습니다. 여기서 어떤부분을 바꾸어야할지 고민해 보았는데, 중복된 값들을 제외하고 넣어야 한다는 생각을 하고 set을 통해 제거해주었습니다.

 

먼저 x값을 deq과 set에 넣습니다.

그 후 while문 안으로 들어가 deq의 첫번째원소의 값, cnt를 얻어낸뒤 pop해줍니다.

calculate에 n을 더한 값, 2를 곱한값, 3을 곱한값을 순서대로 넣어줍니다.

포문을 돌면서 이값이 y와 같다면 현재 cnt+1을 리턴해주고, y보다 크거나 set에 이미 들어와있었다면 넘어가줍니다.

위의 상황이 아닌것들만 deq과 set에 넣어줍니다.

deq이 빌때까지 돌았는데 값을 구하지 못했다면 -1을 리턴해줍니다. 

 

3. 코드

#include <string>
#include <vector>
#include <deque>
#include <set>
#include <iostream>

using namespace std;

int bfs(int x, int y, int n){
    deque<pair<int,int>> deq;
    set<int> s;
    
    if(x==y)
        return 0;
    
    deq.push_back(make_pair(x,0));
    s.insert(x);
    
    while(deq.empty()!=1){
        int num=deq.front().first;
        int cnt=deq.front().second;
        deq.pop_front();
        
        vector<int>calculate(3,0);
        calculate[0]=num+n;
        calculate[1]=num*2;
        calculate[2]=num*3;
        
        for(int i=0; i<3; i++){
            
            if(calculate[i]==y)
                return cnt+1;
            if(calculate[i]>y || s.find(calculate[i])!=s.end())
                continue;
            
            deq.push_back(make_pair(calculate[i],cnt+1));          
            s.insert(calculate[i]);
        }
    }
    return -1;
}

int solution(int x, int y, int n) {
    
    int answer=0;
    answer=bfs(x,y,n);  
    
    return answer;
}