[BOJ/Silver 1] 백준 28280 귀납법(C++)

문제 링크

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

28280번: 귀납법

 

문제

 

입력

첫 줄에는 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)

각 테스트케이스마다 한 줄에 양의 정수 k가 주어진다.

 k의 총합은 4 × 10^6을 넘지 않는다.

 

출력

각 테스트케이스마다 한 줄에, 1에서 시작해서 2배를 하거나 1을 빼는 행동을 최소 몇 번 반복해야 k를 만들 수 있는지 출력한다.

만약 k를 만들지 못한다면, 대신 Wrong proof!를 출력한다.

 

예제 입력 1

2
1
7

예제 출력 1

0
4

 

 

알고리즘 분류

• 그래프 탐색

 

풀이

1에서 시작해서 BFS로 2배를 하거나 1을 빼면서 K를 최소 몇 번 만에 만들 수 있는지 찾는다.

2배를 할 때, 2배를 한 값이 최대 4,000,000이어야 하며, 1을 뺄 때, 1을 뺀 값이 최소 1이어야 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 4000001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, K;
bool Visited[MAX];
int Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Visited[i] = false;
    }
    Answer = INF;
}

void BFS() {
    queue<pair<int, int> > Q;
    Visited[1] = true;
    Q.push(make_pair(1, 0));

    while (!Q.empty()) {
        int NowX = Q.front().first;
        int NowC = Q.front().second;
        Q.pop();

        if (NowX == K) {
            Answer = min(Answer, NowC);
            return;
        }

        if ((NowX * 2 <= MAX) && !Visited[NowX * 2]) {
            Visited[NowX * 2] = true;
            Q.push(make_pair(NowX * 2, NowC + 1));
        }
        if ((NowX >= 2) && !Visited[NowX - 1]) {
            Visited[NowX - 1] = true;
            Q.push(make_pair(NowX - 1, NowC + 1));
        }
    };
}

void settings() {
    init();
    BFS();
}

void find_Answer() {
    cout << Answer << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        cin >> K;
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}