[Baekjoon] 15998번 - 카카오머니 (java)

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

조건 체크

1. 입출금 로그에서 입금 혹은 출금의 값은 2^-1018 ~ 2¹⁰¹⁸ 의 범위이고 0이 아닌 값이다.
   2. 잔액은 0보다크거나 같고 2¹⁰¹⁸ 보단 작은 값이다.
2. 로그가 두개 이상일 때, 이전 로그의 잔액보다 출금 금액이 클 경우 충전이 일어난다.(최소 충전 금액)
3. 충전이 한번일 경우 출력 조건에 의해 충전금액의 약수 중 아무거나 출력하면 정답이다. (두번 이상일 경우 각 충전 금액의 약수를 구하면 됨)
4. 충전을 했을 경우 잔액은 충전금액보다 작아야 한다.
5. 입출금로그에 모순이 생기는 경우도 체크해야한다. 예를들어서 잔액이 10000 인데, 5000을 출금했는데 잔액이 5000이 아닌 값이 들어오거나, 입금을 했는데 잔액이 적어지거나 너무 많아지거나 하는 경우도 체크 필요.

각 로그가 모순이 없는지부터 체크한 후 로그마다 최대공약수를 구해주면 된다.

소스

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int N = Integer.parseInt(bf.readLine());

        long bal = 0;                    // 잔액
        long M = 0;                        // 최소 충전 금액
        long min = Long.MAX_VALUE;
        long a, b;                        // 로그
        long temp = 0;

        boolean valid = true;              // 모순 체크를 위한 변수

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());

            a = Long.parseLong(st.nextToken());
            b = Long.parseLong(st.nextToken());

            // if(valid) {                // valid가 false일 때는 모순이라 더이상 체크하지 않아도됨 (if문이 추가될경우 메모리가 늘어나서 주석처리)
            if ((a + bal) < 0) {
                temp = b - a - bal;

                if (b != 0 && b < min) {
                    min = b;
                }

                if (M == 0) {
                    M = temp;
                } else {
                    M = GCD(M, temp);        // 최대 공약수
                    if (M <= min && min != Long.MAX_VALUE) {
                        valid = false;
                    }
                }
            } else {
                if ((bal + a) != b) {
                    valid = false;
                }
            }
            // }

            bal = b;
        }

        if(valid && M != 0) {
            bw.write(M + "\n");
        } else if(valid && M == 0) {
            bw.write("1\n");
        } else {
            bw.write("-1\n");
        }

        bw.flush();
        bw.close();
    }

    // 최대 공약수를 구하기 위한 유클리드 호제법을 사용
    static long GCD(long a, long b) {
        if(b == 0) {
            return a;
        }

        return GCD(b, a%b);
    }
}