[C++] 상근타워 (백준 3541번)

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

 

#include <iostream>
#include <climits>
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 n, m;
    cin >> n >> m;

    int mina = INT_MAX;

    while (m--) {
        int u, d;
        cin >> u >> d;

        int gcdt = gcd(u, d);
        // lcm = u * d / gcd
        int uc = d / gcdt; // == lcm / u
        int dc = u / gcdt; // == lcm / d
        int zerosum = uc + dc;
        int newn;

        if (n % zerosum == 0) newn = zerosum;
        else newn = n % zerosum;

        int nowf = 0;
        while (newn--) {
            if (nowf - d <= 0) nowf += u;
            else nowf -= d;
        }
        
        if (nowf < mina) mina = nowf;
    }

    cout << mina << '\n';
}

올라가는 층수와 내려가는 층수의 최소공배수를 활용하여 다시 0층으로 내려오는 건 계산없이 제외시키고 그리디하게 선택하여 각 케이스 별로 최소 층을 뽑아냈다. 그런데 태그를 보니까 이분 탐색이네??? 나중에 이분 탐색 풀이도 찾아봐야겠다. (정답)