코딩테스트 -- 숫자 변환하기 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

---

 

..... 간단해 보이네요!

 

 

 

라고 생각해서 

1. x+n

2. x*2

3. x*3

 

길이 세갈래인 dfs 탐색으로 풀어보았습니다...!

 

그러나 실패.... 

#include <string>
#include <vector>

using namespace std;

int N;
int target;

int answer = 987654321;
int visit[1000000]={0};



void find(int n_case,int num,int count){
    if(num==target){
        answer=min(answer,count);
        return;
    }
    
    if(visit[num]!=0 and visit[num]<count){
        return;
    }
    else{
        visit[num]=count;
    }
    
    
    int temp=0;
    if(n_case==0){
        temp=num+N;
    }
    else if(n_case==1){
        temp=num*2;
    }
    else{
        temp=num*3;
    }
    
    
    if(temp>1000001){
        return;
    }
    
    for(int i=0;i<3;i++){
        find(i,temp,count+1);
    }
    
    return;
}


int solution(int x, int y, int n) {
    
    N=n;
    target=y;
    // (x+n)    *2    *3  3가지 
    
    memo.push(x);
    
   
    for(int i=0;i<3;i++){
        find(i,x,0);
    }
    
    
    if(answer==987654321){
        return -1;
    }
    
    return answer;
}

시간 초과가 나는군요..

 

매번 dfs부터 접근해서 틀리고 시작하네요 ㅎㅎ

 

역시 이번 문제는 bfs 탐색방법을 사용해야 하는 문제였습니다.

 

변수는 아래처럼 queue 변수와 방문체크 배열을 선언해주고

int N;

int answer = 987654321;
queue<pair<int, int>> memo;
int visit[1000000]={0};

 

조건 3개는 아래처럼 따로 함수를 만들어 통과했습니다.

int cal(int n_case, int num) {
    int temp = 0;
    if (n_case == 0) {
        temp = num + N;
    }
    else if (n_case == 1) {
        temp = num * 2;
    }
    else {
        temp = num * 3;
    }
    return temp;
}

 

 

그리고 bfs! while 내부에서 조건을 판별하여 push pop 해주는 기본적인 구조....

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

    N = n;
    // (x+n)    *2    *3  3가지 
    if (x == y) {
        return 0;
    }
    memo.push({ x,0 });

    while (!memo.empty()) {
        pair<int, int>temp = { memo.front().first,memo.front().second };
        int cal_temp = 0;
        memo.pop();
        
        if(memo.front().second>answer){
            continue;
        }
        
        for (int i = 0; i < 3; i++) {
            cal_temp = cal(i, temp.first);

            if (cal_temp == y) {
                answer=min(answer,temp.second+1);
            }
            else if (cal_temp < y and visit[cal_temp]!=1) {
                memo.push({cal_temp,temp.second+1});
                visit[cal_temp]=1;
            }
        }
    }

 

끝...! 

 

 

목적지까지의 경로가 필요한 문제는 DFS!

목적지까지의 최단거리/ 비용 등이 필요하면 BFS! (거의 무조건 유리함!!!)

 

다음 문제풀때는 생각 하며 풀어야겠습니다....

 

 

 

ALL

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

int N;

int answer = 0;
queue<pair<int, int>> memo;

int cal(int n_case, int num) {
    int temp = 0;

    if (n_case == 0) {
        temp = num + N;
    }
    else if (n_case == 1) {
        temp = num * 2;
    }
    else {
        temp = num * 3;
    }
    return temp;
}

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

    N = n;
    // (x+n)    *2    *3  3가지 
    if (x == y) {
        return 0;
    }

    memo.push({ x,0 });

    while (memo.empty()) {
        pair<int, int>temp = { memo.front().first,memo.front().second };
        int cal_temp = 0;
        memo.pop();

        for (int i = 0; i < 3; i++) {
            cal_temp = cal(i, temp.first);

            if (cal_temp == y) {
                return answer + 1;
            }
            else if (cal_temp < y) {
                memo.push({cal_temp,temp.second+1});
            }
        }

        answer += 1;

    }



    if (answer == 987654321) {
        return -1;
    }

    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!