[백준/c++] BOJ 28280 - 귀납법

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

28280번: 귀납법

 

문제 설명

1. n = k일 때 성립하면 n = 2k 일 때도 성립한다.

2. n = k > 1 일 때 성립하면 n = k - 1일 때도 성립한다.

양의 정수 k가 주어질 때, 정수 1에서 시작하여 현재 값을 2배 하거나 1을 뺀 값으로 바꾸는 행동을 몇 번 해야 k를 만들 수 있는지 계산한다. 

테스트 케이스 개수 T (1 <= T <= 20)

해결

간단한 bfs 문제이다. 현재 값의 2배를 하거나 1을 뺀 값으로 k를 만들어야 하므로 각각의 테스트 케이스마다 bfs를 돌려 준다. 현재 값에 현재 값, 혹은 -1을 더해 주는 방식으로 반복문을 구현했다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int visited[4000005];

int bfs() {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    q.push({ 1, 0 });
    visited[1] = 1;

    while (1) {
        auto cur = q.front(); q.pop();
        for (auto i : { cur.x, -1 }) {
            int nx = cur.x + i;
            if (nx <= 0 || nx > 4000000 || visited[nx]) continue;
            if (nx == m) return cur.y + 1;
            q.push({ nx, cur.y + 1});
            visited[nx] = 1;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    while (n--) {
        cin >> m;
        if (m == 1) cout << 0 << "\n";
        else {
            int bf = bfs();
            if (bf == -1) cout << "Wrong proof!\n";
            else cout << bf << "\n";
        }
    }
}