[Level2.] 숫자 변환하기 C++

<< 문제 >>

 

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

프로그래머스

 

 

2배, 3배 +n 

이 세 가지 연산으로 x를 y로 변환하는 최소 횟수를 찾는 문제입니다. 

 

이 가능한 연산 경우가 적어서 모든 경우를 다 볼 수 있는데,

주의해야 할 부분은 x -> y 보다 y -> x가 적은 경우를 계산한다는 것입니다. 

 

예를 들어 1, 10이라면 

 

1부터 시작하면 2, 3을 모두 곱하는 경우를 택하겠지만, 10부터 시작한다면 2로만 나눌 수 있겠죠?

 

이게 반복하다보면 많은 차이를 만들 수 있습니다. 

 

주요 과정은

 

1. y에서 /2 , /3 , -n 연산이 가능하다면 연산을 한다.

2. 연산 결과가 x와 일치한다면 끝내고, 아니라면 반복한다.

3. q에 더 이상 수가 없다면 ( 3가지 연산이 불가능한 상태 == 즉, x로 y를 만들 수 없을 때) 1을 출력

 

어짜피 무슨 연산을 하든 상관이 없으니 같은 연산 횟수의 수끼리 한 q에 담기게 됩니다.

 

x = 3  , y = 23 , n = 1 이라면

 

q = [23]

1: => q = [22]      

2: => q = [11, 21]

3: => q = [10, 7, 20]

4: => q = [5, 9, 6, 10, 19]

5: => q = [4, 3, ...]

 

그러면 이렇게 5번째가 최소라는 것을 알 수 있습니다. 

 

 

<< Code >> 

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

using namespace std;

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

    if(x == y){
        return 0;
    }
    
    queue<int> q;
    q.push(y);
    
    int qSize;
    int head;
    int num;
    bool isOver = false;
    
    while(!isOver && !q.empty()){
        qSize = q.size(); 
        for(int i = 0; i < qSize; i++){
            head = q.front();
            if(head % 2 == 0){
                num = head / 2;
                if(num == x) { 
                    isOver = true; 
                    break;
                }
                q.push(num);
            }
            
            if(head % 3 == 0){
                num = head / 3;
                if(num == x) { 
                    isOver = true; 
                    break;
                }
                q.push(num);
            }
            
            if(head >= n){
                num = head - n;
                if(num == x) { 
                    isOver = true; 
                    break;
                }
                q.push(num);
            }
            q.pop();
        }
        answer++;
    }
    
    if(!isOver){
        answer = -1;
    }
    
    return answer;
}

 

 

<< GitHub >>

https://github.com/J2on/StudyAlgorithm_Part2/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/154538.%E2%80%85%EC%88%AB%EC%9E%90%E2%80%85%EB%B3%80%ED%99%98%ED%95%98%EA%B8%B0/%EC%88%AB%EC%9E%90%E2%80%85%EB%B3%80%ED%99%98%ED%95%98%EA%B8%B0.cpp