코딩테스트/구현|기타

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

유(YOO) 2023. 9. 15. 17:05

 

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

 

15998번: 카카오머니

만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면

www.acmicpc.net

#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;
}