[BOJ] 15998 : 카카오머니 - java

문제

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

---

문제풀이

입출금 로그의 유효성을 체크하는 문제이기 때문에 입력받은 N개의 a(입출금액)와 b(잔액)를  배열에 넣은 후 검증한다.

입금 시 전 잔액 대비 현 잔액이 유효한지 체크한다.
출금 시 잔액이 마이너스가 되는 경우 최소 금액 M을 충전해야 한다. M은 모든 충전의 공통의 약수를 가지며 잔액이 최소의 값이 되게 하는 금액이므로 최대 공약수가 되어야 한다.
최대공약수를 구하는 gcd(유클리드 호제법)를 사용한다.

문제의 요구대로 "-1"을 출력해야할 예외케이스가 있다.
▶ 입금시, 현 잔액이 전 잔액과 입금액의 합과 맞지 않는 경우
▶ 최소 충전 단위보다 더 많이 출금한 경우
▶ 이전 잔액보다 적게 출금했는데 잔액이 맞지 않는 경우

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _15998 {
    static int N;
    static long M = 0; // 최소 충전 단위
    static long[] a, b; // a : 입출금액 , b : 잔액

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        a = new long[N + 1];
        b = new long[N + 1];
        for (int i = 1; i <= N; ++i) {
            st = new StringTokenizer(br.readLine());
            a[i] = Long.parseLong(st.nextToken());
            b[i] = Long.parseLong(st.nextToken());
            M = gcd(M, b[i] - b[i - 1] - a[i]);
        }
        for (int i = 1; i <= N; ++i) {
            if (b[i] - b[i - 1] == a[i]) continue; // 정상
            
            /* 예외케이스 */
            if (a[i] > 0 // 입금인데 정상이 아닌 경우
                    || (M > 0 && M <= b[i]) // 최소 충전 단위보다 많이 출금한 경우
                    || -a[i] < b[i - 1] // 잔액보다 적게 출금했는데 맞지 않는 경우
            ) {
                System.out.print(-1);
                return;
            }
        }
        System.out.print(M > 0 ? M : 1); // M이 0이면 입금만 일어난 경우이다
    }

    /* 유클리드 호제법 */
    static long gcd(long a, long b) {
        while (b != 0) {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return Math.abs(a);
    }
}

---

etc

최대공약수(gcd)를 이용해야 한다는 점과 예외케이스를 캐치해야 풀이가 가능한 문제였다.

https://djun95.tistory.com/8

유클리드 호제법(Euclidean Algorithm)