[구현(최대공약수(GCD))] (CHECK) 백준 15998 카카오머니 C++

 

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

15998번: 카카오머니

#include <iostream>
#define INF 9 * 1e18

using namespace std;

long long gcd(long long a, long long b) {
    return (b == 0)? a : gcd(b, a % b);
}

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

    int n;
    cin >> n;

    long long money = 0; // 잔액 (0 < 최대 잔액(과충전) maxB <= 충전 금액 m)
    long long answer = INF; // 최소 충전 단위 = m의 최솟값 = 모든 충전 금액의 최대공약수
    long long maxB = 0; // 최대 잔액

    long long a, b;
    for(int i=0; i<n; i++) {
        cin >> a >> b;

        if (answer == -1) break;
        
        if (a < 0) { // 출금
            if (money + a < 0) { // 잔액 부족
                long long m =  b - money - a; // 충전 금액
                if (answer != INF) m = gcd(answer, b - money - a);
                maxB = max(maxB, b);

                if (m < maxB) answer = -1; // 잔액 범위
                else if ((m == 1) && (b != 0)) answer = -1; // 최대공약수 1일 때, 무조건 잔액 0
                else answer = min(answer, m);
                money = b;
                continue; // 이어서
            }
        }

        // 입출금
        money += a;
        if (money != b) answer = -1;
    }

    if (answer == INF) answer = 1;
    cout << answer;

    return 0;
}

#include <iostream>
#define INF 9 * 1e18

using namespace std;

long long gcd(long long a, long long b) {
    long long tmp;
    if (a < b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    while (b) {
    	tmp = a % b;
    	a = b;
        b = tmp;
    }
    return a;
}

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

    int n;
    cin >> n;

    long long money = 0; // 잔액 (0 < 최대 잔액(과충전) <= 충전 금액)
    long long answer = INF; // 최소 충전 단위 = 모든 충전 금액의 최대공약수
    long long maxB = 0; // 최소 잔액

    long long a, b;
    for(int i=0; i<n; i++) {
        cin >> a >> b;

        if (answer == -1) break;
        
        if (a < 0) { // 출금
            if (money + a < 0) { // 잔액 부족
                long long m =  b - money - a; // 충전 금액
                if (answer != INF) m = gcd(answer, b - money - a);
                maxB = max(maxB, b);

                if (m < maxB) answer = -1; // 잔액 범위
                else if ((m == 1) && (b != 0)) answer = -1; // 최대공약수 1일 때, 무조건 잔액 0
                else answer = min(answer, m);
                money = b;
                continue; // 이어서
            }
        }

        // 입출금
        money += a;
        if (money != b) answer = -1;
    }

    if (answer == INF) answer = 1;
    cout << answer;

    return 0;
}