[C++] 개구리 (백준 25333번)

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

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int a, b, x;
        cin >> a >> b >> x;

        vector<bool> chk(x + 1, false);
        queue<int> q;
        q.push(0);
        chk[0] = true;

        int cnt = 0;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            int right = cur + a;
            if (right <= x && !chk[right]) {
                q.push(right);
                chk[right] = true;
                cnt++;
            }
            int left = cur - b;
            if (left > 0 && !chk[left]) {
                q.push(left);
                chk[left] = true;
                cnt++;
            }
        }

        cout << cnt << '\n';
    }
}

처음엔 이렇게 무지성 bfs 코드를 짰다. x가 2022까지는 잘 되는 듯 한데 x가 2000000000이 되니까 결과가 안 나온다. 아마 벡터 크기 제한 때문인 것 같다. 그리고 x 범위가 너무 크니까 이렇게 하면 안 된다는 생각이 들었고 상근타워 문제가 생각났다. 태그는 이분탐색이지만 나는 최소공배수를 활용하여 풀었다.
상근타워 문제의 내 풀이: https://jungh150c.tistory.com/132

 

#include <iostream>
#include <vector>
using namespace std;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd (y, x % y);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int a, b, x;
        cin >> a >> b >> x;
        cout << x / gcd(a, b) << '\n';
    }
}

최대공약수를 이용한 풀이이다. 테스트 케이스 하나당 코드가 3줄밖에 없는 (gcd 함수 포함해도 5줄) 엄청 간단한 코드가 되었다. 상큰타워랑 약간 다르긴 하지만 아이디어는 비슷한 것 같다. 최소공배수/최대공약수를 이용하여 불필요한 연산을 확 줄이는 것. (AC)