[BOJ] 백준 15998번 : 카카오머니 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/15998

15998번: 카카오머니

문제

카카오페이는 카카오톡을 통해 송금, 결제 등을 할 수 있는 핀테크 서비스이다. 카카오페이에는 원하는 만큼 현금을 충전하고 사용할 수 있는 카카오머니라는 서비스가 있다. 무지는 오늘부터 현금을 간편하게 사용할 수 있는 카카오머니를 사용해 보기로 하였다. 무지는 좀 더 편리하게 서비스를 이용하기 위해 잔액이 10100 원인 자신의 계좌와 카카오머니 계정을 연결하였다.

처음에 무지의 카카오머니 잔액은 0원이다. 무지가 자신의 통장에서 잔액을 충전하거나 타인에게 송금을 받을 경우 카카오머니 잔액이 증가하며, 이러한 경우를 입금이라고 한다. 또한, 무지가 카카오머니로 결제를 하거나 타인에게 송금을 할 경우 카카오머니 잔액이 감소하며, 이러한 경우를 출금이라고 한다. 이 문제에서는 입금 또는 출금할 때 액수가 1원 단위여야 한다는 것 외의 별다른 제약이 없다고 가정하자. 즉, 실제 카카오머니의 제약사항인 잔액 200만 원 이하, 송금은 1일에 50만 원 한도 등은 무시한다.

x 원이 입금될 경우, 무지의 카카오머니 잔액은 x 원만큼 증가한다. 그러나, x 원을 출금할 때는 상황이 다르다. 만약 잔액이 x 원 이상이라면, 잔액에서 x 원을 차감하면 된다. 그러나, 잔액이 x 원 미만이라면 카카오머니 내부에서 금액을 충당할 수 없기 때문에, 연결된 통장에서 돈을 가져올 필요가 있다. 카카오는 이를 위해 최소 충전 단위 M 을 두어서, 잔액이 x 원 이상이 되기 전까지 M 원을 통장에서 가져오다가, 잔액이 x 원 이상이 되면 x 원을 잔액에서 차감한다. M 은 양의 정수이다.

예를 들어, M = 10,000 이고 무지의 잔액이 1,500원일 때, x = 17,000원을 출금하려는 상황을 가정하여 보자. 무지의 잔액으로는 x = 17,000원을 만들 수 없기 때문에, 카카오머니는 우선 무지의 계좌에서 M = 10,000원을 가져와 잔액을 11,500원으로 만든다. 그러나, 11,500원으로도 x = 17,000원을 만들 수 없기 때문에, 카카오머니는 무지의 계좌에서 또 M = 10,000원을 가져와 잔액을 21,500원으로 만든다. 이제는 17,000원을 출금할 수 있으므로, 잔액에서 x = 17,000원을 차감한다. 최종적으로, 무지의 카카오머니 잔액은 21,500 - 17,000 = 4,500원이 된다.

카카오머니에 남는 입출금 내역과는 별개로, 무지는 카카오머니를 이용하기 시작할 때부터 자신만의 입출금 로그를 작성하였다. 이 로그는 N 개의 두 정수 쌍 (ai, bi)로 이루어져 있으며, 시간 순서대로 저장되어 있다. 무지는 꼼꼼하기 때문에 입금 또는 출금 내역을 로그에서 하나도 빠뜨리지 않았다고 생각한다. 각 쌍의 의미는 아래와 같다.

• ai > 0이라면, 무지의 카카오머니에 ai 원이 입금되었다. 입금 결과, 잔액은 bi 원이었다.
• ai < 0이라면, 무지의 카카오머니에서 -ai 원이 출금되었다. 출금 결과, 최종적으로 잔액은 bi 원이었다.
• ai = 0인 경우는 없다.

위에 언급된 예시의 경우, 무지의 입출금 로그에 (-17,000, 4,500)이 추가되었을 것이다.

그러나 무지는 자신이 제대로 로그를 관리하고 있는지에 대한 걱정이 들기도 해서, 간단하게 로그에 모순이 없는지를 점검해 보고자 한다. 무지가 생각한 방법은, 입출금 로그만 보고 유효한, 즉 로그에 모순이 생기지 않도록 하는 최소 충전 단위 M 이 존재하는지, 존재한다면 값이 얼마인지 확인하는 것이다. 무지를 도와, 이 일을 대신해 줄 프로그램을 작성하라.

 

풀이

최대공약수를 이용한다는 점만 캐치하면 로직은 구현하기에 어렵지 않는 문제였습니다. 다만, 생각지도 못한 예외케이스가 꽤 많았고, 저는 최대공약수를 list에 담아서 한 번에 처리하려다가 시간초과가 났습니다.

지금부터 제가 구현한 로직을 설명드리도록 하겠습니다.

먼저, 0원에서 시작한 카카오머니 잔액에 초점을 맞춰봅시다. a는 양수 또는 음수인데, 양수일 때는 잔액에 입금을 하고, 음수일 때는 잔액에서 출금을 합니다.

여기서 우리는 case를 2가지로 나눌 수 있습니다.

 

1. 입금을 하거나, 출금할 때 잔액이 양수인 경우 (balance + a >= 0)

이 상황에서는 단순히 과거 잔액이었던 balance를 b로 초기화 해 주면 됩니다.

 

2. 출금을 했는데, 잔액이 음수인 경우 (balance + a < 0)

좀 더 풀어 쓰자면, 출금을 하려고 했으나 현재 카카오머니 잔액이 부족해서 최소 출금 금액인 M만큼 계좌에서 카카오머니 잔액에 넣어줘야 하는 경우입니다.

이것을 식으로 한 번 써 보겠습니다.

(balance + M * n) + a = b     -> n, M을 출금한 횟수이고, a는 음수로 들어오므로 식에서 +a로 써도 무방합니다.

M * n = b - a - balance

여기서, M * n은 자동 충전액을 의미하고, 모든 자동 충전액은 M을 약수로 가진다는 사실을 알 수 있습니다.

즉, 우리가 할 일은 이제 로그를 분석하면서 2번 case에 해당하는 경우, M을 최대공약수로 초기화해 주는 것입니다.

 

전체적인 틀은 위와 같습니다. 하지만, 예외케이스에 대해서 처리를 해 주어야 합니다. 각 case 별로 예외를 처리해 보겠습니다.

 

예외 처리

1. 입금을 하거나, 출금할 때 잔액이 양수인 경우 (balance + a >= 0)

문제를 풀다보면, M에 대해서만 집중하기때문에 이 case에서 놓치기 쉬운 부분이 하나 있었습니다.

M이 필요하지 않을 떄, 입출금 로그 자체가 잘못된 것이지요. 가령, 다음과 같은 로그가 있다고 가정해 봅시다.

 

2

300 300

500 700

 

300 + 500 = 800이 되어어야하지만, 로그 상으로 잔액은 700으로 표시되어있기때문에 이것은 잘못된 로그라고 판단할 수 있습니다.

즉, balance + a != b일 경우, 우리는 이 로그가 잘못되었다고 할 수 있는 것입니다.

 

2. 출금을 했는데, 잔액이 음수인 경우 (balance + a < 0)

여기서의 예외는 하나가 존재합니다.

바로, M이 거래 후 잔액인 b보다 작거나 같은 경우입니다. 문제에서 M은 가능한 최소의 출금 금액이라고 명시했기때문에 M은 항상 b보다 커야합니다.

다만, 어떤 상황에서든 M <= b를 적용하는 것이 아니라 매 순간마다 b의 최솟값인 minB를 하나 정의해서 그것과 비교하였습니다. (단, minB가 0이 되어서는 안 됩니다.)

minB를 사용하는 이유는 예시를 통해 알아봅시다.

 

2

-250 50

-400 10

 

balance = 0, a = -250, b = 50이므로 minB = 50이 되고, (자동 충전액) = 300이므로 M = 300이 됩니다.

그리고 balance = 50으로 초기화됩니다.

balance = 50, a = 400, b = 10이므로 minB = 10이 되고, (자동 충전액) = 360 이므로 M = GCD(300, 360) = 60이 됩니다.

 

위 과정을 보면, minB가 50일 때 M은 300이고, minB가 10일 때는 M이 60이 되는 사실을 알 수 있습니다. 즉, minB가 작아질수록 최소의 M을 구할 수 있는 것입니다.

그리고 이 M과 minB을 비교함으로써 모순인지 아닌지 판단이 가능합니다.

예시를 하나 더 봅시다.

 

2

-250 50

-400 0

 

balance = 0, a = -250, b = 50이므로 minB = 50이 되고, (자동 충전액) = 300이므로 M = 300이 됩니다.

그리고 balance = 50으로 초기화됩니다.

balance = 50, a = 400, b = 0이므로 minB = 50(b가 0일 때는 초기화x)이 되고, (자동 충전액) = 350 이므로 M = GCD(300, 350) = 50이 됩니다.

이 때, M <= minB이므로 위에서 언급한 모순에 해당합니다.

 

3. M이 사용되지 않은 경우

1번 case의 예시처럼 M 자체가 사용되지 않을 수도 있습니다. 이 때는 임의의 수 하나를 출력하라고 했기때문에 저는 M = 1로 두었습니다.

 

풀이와 예외 처리를 모두 수행한 것이 아래 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
 
        long a, b;
        long minB = (long) 10e18; // 아래서 언급될 b의 최솟값
        long balance = 0; // 현재 잔액
 
        boolean valid = true;
        long M = 0; // 최소 출금 금액
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            a = Long.parseLong(st.nextToken()); // 입금 또는 출금액
            b = Long.parseLong(st.nextToken()); // 입금 또는 출금을 한 뒤 남은 잔액
 
            // 현재 잔액에서 출금액을 뻈을 때, 음수가 나올 경우
            // 계좌에서 M만큼 출금해야 함.
            if (balance + a < 0) {
                // (balance + M x n) + a = b -> n은 M을 출금하는 횟수.
                // M x n = b - a - balance
                // 자동 충전액에 대한 식은 M x n이므로
                // 모든 자동 충전액은 M을 약수로 가진다는 사실을 알 수 있다.
                // 결과적으로, 이 조건을 만족하는 반복문을 돌 때마다 M은 최대공약수로 초기화해주면 된다.
                // M의 임시 변수를 temp를 두었음.
                long temp = b - a - balance;
 
                // minB는 b의 최솟값이 되도록 초기화.
                if (b != 0 && b < minB) {
                    minB = b;
                }
 
                if (M == 0) {
                    // M이 0일 떄는
                    // 단순히 temp를 대입하면 됨.
                    M = temp;
                } else {
                    // M이 0이 아닐 떄는
                    // M과 temp의 최대공약수를 구해서
                    // M에 대입함.
                    M = GCD(M, temp);
 
                    // 출금 또는 입금을 하고 난 뒤, minB가 M보다 크거나 같으면 모순.
                    // 단, minB = (long)10e18일 때는 minB의 초기 상태이므로
                    // 위의 모순이 생기더라도 무시할 수 있음.
                    if (M <= minB && minB != (long) 10e18) {
                        valid = false;
                        break;
                    }
                }
            } else { // 현재 잔액에서 입금을 하거나, 현재 잔액을 초과하지 않는 만큼 출금을 할 경우
                // 현재 잔액에서 입금하거나 출금을 한 결과가 b와 다르면 모순.
                if (balance + a != b) {
                    valid = false;
                    break;
                }
            }
 
            // 과거 잔액을 현재 잔액으로 초기화.
            balance = b;
        }
 
        if (valid && M != 0) {
            // 모순이 발생하지 않았고, M이 1이상의 최대 공약수를 가진 경우
            bw.write(M + "\n");
        } else if (valid && M == 0) {
            // 모순이 발생하지 않았으나, 입금 또는 출금을 했을 때
            // 현재 잔액이 음수가 발생하지 않아서 M을 계산할 일이 없던 경우
            bw.write("1\n");
        } else {
            // 모순이 발생한 경우
            bw.write("-1\n");
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 유클리드 호제법
    public static long GCD(long a, long b) {
        while (b > 0) {
            long tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.