[백준 1463] 1로 만들기

문제 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

문제 분석 

수가 입력 되고 그 수가 3으로 나눠지면 3으로 나누고, 2로 나눠지면 2로 나누고, 안 나눠진다면 1을 뺴는 간단한 문제다. 

 

 

알고리즘 설계

수가 2로 나눠지면 2를 나눈 값을 넣고, 3으로 나눠진다면 3으로 나누고, 다 아니라면 1을 뺸다. 

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int index;
    queue<pair<int, int>> q;

    cin >> index;
    q.push(make_pair(index, 0));

    while (!q.empty())
    {
        if (q.front().first == 1)
            break;

        if (q.front().first % 2 == 0)
            q.push(make_pair(q.front().first / 2, q.front().second + 1));
        if (q.front().first % 3 == 0)
            q.push(make_pair(q.front().first / 3, q.front().second + 1));
        q.push(make_pair(q.front().first - 1, q.front().second + 1));
        q.pop();
    }

    cout << q.front().second;
}

 

 

queue가 아니여도 풀 수 있을 것이다.