[BOJ] 15998:카카오머니

0. 문제

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

15998번: 카카오머니

 

1. 문제분석

- 출금하는 금액에 따라 잔액이 음수가 될 때, 음의 값을 갖는 잔액을 양의 값으로 바꾸기 위해서는 최소금액 m을 적어도 1번 이상 채워야 한다. 즉, 잔액이 음수가 되었을 때, 이를 메우기 위해 더해지는 금액들은 모두 공통의 약수를 가지며, 더해지는 금액은 항상 잔액이 최소의 양수 값이 되게 하는 금액이므로 그 약수는 최대공약수가 된다. 따라서 최대공약수(gcd)를 구하는 유클리드 호제법을 사용해 문제를 풀어야 한다. 

 

2. 주의할 점

- 유클리드 호제법 Euclidean Algorithm

• 주어진 두 수의 최대 공약수를 구하기 위한 알고리즘.
• "두 수 A, B(A>=B)에 대하여, A와 B의 최대공약수는, B와 A % B(A를 B로 나눈 나머지)의 최대공약수와 같다."라는 명제를 이용한다.
• 두 수 A, B 그리고 A % B = r 이라고 할 때, r의 값을 구하고 이를 B로, 기존의 B값은 A로 놓고 다시 새로운 r 값을 구한다. 만약 구한 r의 값이 0이라면, B가 A의 약수가 되는 것이므로 이 때의 B 값이 맨 처음의 A, B 두 수의 최대공약수가 된다. 

- 조건을 만족하지 않는 예외 사항들이 꽤나 여러가지가 있다.

• 입금만 했는데도, 현재의 잔액이 바로 전 단계의 잔액과 입금액의 합과 맞지 않는 경우
• 최소 출금 금액보다 더 많이 출금한 경우
• 이전 잔액보다 적게 출금했는데도 잔액이 맞지 않는 경우

 

3. 소스코드(Java)

// boj 15998 카카오머니
// gcd, 유클리드 호제법

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

public class boj_15998 {
    static int n;
    static long m = 0;
    static long[] a, b;
    public static void main(String[] args) throws Exception{
        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] = stol(st.nextToken());
            b[i] = stol(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 stol(String s) { return Long.parseLong(s);}
    static long gcd(long a, long b) { // a >= b로 가정. 만약 a < b라고 해도, 첫 a%b를 하면 몫이 0, 나머지가 a가 되므로 a b가 swap됨
        while (b != 0) {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return Math.abs(a);
    }
}

 

4. 여담

- 카카오 코드페스티벌 2018 본선 문제이다. 카카오의 친절한 해설까지 있다.

- 예외적으로 생각해야 할 사항들이 꽤 많았다. 예외 케이스를 밝혀내는 연습을 좀 더 많이 해야할 듯..

- 유클리드 호제법 증명 [출처]