[C/C++] 백준 1463번 1로 만들기

 

 

 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue> // 큐

using namespace std;

int solution(int x, int y=1) {

    vector<int> visited(1000000, 0); // 1<= N <= 1,000,000 (10^6)
    queue<pair<int, int>> q; // int : x에 /2,/3,-1 진행한 값 , int : 연산 횟수 

    if (x == y) { // x,y의 값이 시작부터 같은 경우 
        return 0;
    }else{
        q.push({ x,0 }); // int : x에 /2,/3,-1 진행한 값 , int : 연산 횟수 
    }
    // first : x에 /2,/3,-1 진행한 값, second : 연산 횟수 
    while (!q.empty()) {
        auto Qnum = q.front(); // Qnum -> q값 저장
        q.pop();

        if (Qnum.first - 1  >= y && visited[Qnum.first -1] == 0) { // -1을 하고, -1을 한 결과값이 처음 나왔을 경우 (첫 방문)
            visited[Qnum.first - 1]++; // 방문 표시로 증감연산 

            if (Qnum.first - 1 == y) { // y값과 같아졌을 때 
                return Qnum.second + 1; // 연산 횟수 증감 후 리턴 
            }
            else {
                q.push({ Qnum.first - 1,Qnum.second + 1 }); // 아닐 경우 연산한 값과 연산 회수 q에 삽입
            }
        }

        if (Qnum.first % 2 == 0 && visited[Qnum.first / 2] == 0) { // 2로 나눠지는 경우와 처음 방문 했을 경우
            visited[Qnum.first / 2]++;

            if (Qnum.first / 2 == y) {
                return Qnum.second + 1;
            }
            else {
                q.push({ Qnum.first / 2,Qnum.second + 1 });
            }
        }

        if (Qnum.first % 3 == 0 && visited[Qnum.first / 3] == 0) { // 3으로 나눠진 경우와 처음 방문 했을 경우
            visited[Qnum.first / 3]++;

            if (Qnum.first / 3 == y) {
                return Qnum.second + 1;
            }
            else {
                q.push({ Qnum.first / 3,Qnum.second + 1 });
            }
        }
    }
}

int main()
{
    int N;
	cin >> N;

    cout<<solution(N);

	return 0;
}