백준 1463] C++ 1로 만들기

해당 문제는 백준 사이트에서 풀 수 있습니다.

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

※백준 사이트를 풀 때 다른 코딩테스트 사이트와는 다르게 입력과 출력을 해줘야 합니다.

그리고 cout << 로 출력을 해주면 출력하는 속도가 굉장히 느려지기 때문에 printf를 사용하셔야 합니다.

cout<< 와 printf는 함수와 클래스 차이 때문에 cout<<가 디어셈블리상으로 본다면 훨씬 많은 호출이 이뤄지게 됩니다.

1. 문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

2. 풀이

숫자 N을 3, 2로 나누거나 1을 뺏을 때 가장 빨리 1을 만드는 횟수를 구하는 것입니다.

queue를 이용해 쉽게 구현할 수 있습니다.

풀이법은 간단합니다. 모든 경우의 수를 queue에 다 때려 넣으면 됩니다.

1. n % 3 = 0 이면, n / 3으로 나눴을 대 나누어 떨어진다면 q에 넣습니다.

2. n % 2 = 0 이면, n / 2으로 나눴을 대 나누어 떨어진다면 q에 넣습니다.

3. n - 1 != 0 이면, n - 1한 값을 q에 넣습니다.

이렇게 된다면 첫 바퀴를 돌았을 때 만족하는 조건의 수가 모드 queue에 들어갑니다.

10으로 한다면 첫 바퀴 때 queue에는 5와 9가 들어갈 것입니다.

두번째 바퀴 때는 5를 가지고 위와 같은 식을 구합니다.

그러고 나면 queue 에는 [9, 4]가 들어갈 것이고

3바퀴를 돌면 queue 에는 [4, 3, 8] 이 들어갈 것입니다.

이런식으로 1이 나올 때 까지 계속 돌리면 가장 적은 횟수를 구할 수 있습니다.

또한 중복계산을 막기위해 check배열을 만들어 해당 값이 전에 나왔는지 체크해 준다면

중복검사를 막아 좀 더 빠르게 구현할 수 있습니다.

예를 들어 8 / 2 = 4가 나왔는데, 5 - 1 = 4가 된다면 이미 4는 한번 계산을 마쳤기 때문에 넘어가도 됩니다.

왜냐? 4를 바탕으로 이미 계산이 이뤄졌기 때문입니다. 

3. 코드

#include <iostream>

#include <queue>

#include <cstdio>

using namespace std;

queue<pair<int, int>> q;

bool check[1000001];

int dfs(queue<pair<int, int>>& q) {

    int n = 0, num = 0;

    n = q.front().first;

    num = q.front().second;

    q.pop();

    if (n == 1) return num;

    

    if (n % 3 == 0 && !check[n / 3]) 

        q.emplace(n / 3, num + 1);

    

    

    if (n % 2 == 0 && !check[n / 2]) 

        q.emplace(n / 2, num + 1);

    

    if (n - 1 > 0 && !check[n - 1]) 

         q.emplace(n - 1, num + 1);

     

    check[n] = true;

    return dfs(q);

}

int main() {

    int n;

    cin >> n;

    q.emplace(n, 0);

    printf("%d ", dfs(q));

    return 0;

}