15998. 카카오머니 (Python)

15998번: 카카오머니

 

 

풀이

 계좌에서 충전이 필요한 출금 작업을 할 때마다 충전에 필요한 최대 금액들에 대한 최대 공약수를 구하고 구한 값을 M으로 설정했을 때 로그에 모순이 생기지 않는지를 체크한다.

 

 

 문제의 예제에서 충전이 필요한 출금 작업은 두 건 존재한다. 

 

 (1)번 로그의 경우 충전이 필요한 첫 출금 작업이므로 계산에 필요한 값들을 기록하면 된다. 여기에서 필요한 값은 충전해야 하는 20,000원에 대한 정보와 출금 후 남은 잔액인 4,500원이다. 

 

 (2)번 로그의 경우 총 10,000원 충전이 필요하다. 이제 이전에 기록한 충전해야 하는 금액인 20,000과 현재 로그에서 필요한 충전 금액인 10,000에 대하여 최대 공약수를 구한다. 두 수의 최대 공약수는 10,000이다. 

 이제 출금 후 잔액의 최댓값을 설정해야 한다. 이전에 4,500을 기록했고 현재 잔액은 9,900이다. 두 수중 최댓값은 9,900이다. 이제 이 9,900과 최대 공약수 10,000을 비교한다. 최대 공약수가 더 큰 값을 가지므로 최소 충전 금액 M을 10,000으로 설정하면 위의 로그는 유효한 로그가 됨을 알 수 있다.

 

 여기에서 잔액의 최댓값과 충전 금액의 최대 공약수를 왜 비교하는지 이해가 안갈 수 있는데 (1)번 로그를 생각해보자. 총 20,000원을 충전하기 위해서는 20,000원을 1번 충전할 수도 있고 5,000원을 4번 충전할 수도 있다. 그럼 4,000원을 5번 충전해도 될까? 4,000원을 4번 충전하고 나면 카카오머니의 잔액은 17,500원이 되어 17,000원을 출금할 수 있는 상태가 된다. 그렇기 때문에 잔액은 500원이 된다.

 만약 출금에 필요한 금액이 1,501원이라고 가정해보자(출금을 위해 충전이 필요한 금액 중 최소 금액). 4,000원을 충전하면 카카오머니의 잔액은 5,500원이 되고 1,501원을 출금하면 3,999원이 남는다. 결과적으로 4,000원씩 충전을 하면 발생할 수 있는 잔액의 경우는 0원 ~ 3,999원임을 알 수 있다. 

 

 위의 예제가 다음과 같이 마지막 로그의 잔액이 3,900원이 된다고 가정해보자. 

 (2)번 로그에서 20,000과 4,000의 최대 공약수는 4,000이 된다. 출금 후 잔액의 최댓값은 4,500이 된다. 이제 4,000과 4,500을 비교하면 4,500이 더 크므로 4,000원을 최소 충전 단위인 M으로 설정할 수 없음을 알 수 있다. 그렇기 때문에 위의 예제 로그에서는 M을 찾을 수 없으므로 유효하지 않은 로그가 되고 답은 -1이 된다. 

 

코드

import sys
input = sys.stdin.readline
LIMIT = 9 * (10 ** 18)


# 두 수의 최대공약수를 구하기 위한 함수
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


if __name__ == '__main__':
    N = int(input())
    firstWithdraw = True # 첫 출금인지를 확인하기 위한 flag
    kakaoMoney = 0 # 카카오 머니의 잔액
    maxM = 0 # 출금 이후에 남은 잔액 중 가장 큰 값
    res = 1 # 출력할 M

    for _ in range(N):
        a, b = map(int, input().split())

        if res == -1: # M이 존재하지 않을 경우 추가 작업을 하지 않는다
            continue
        
        # (1) 계좌에서 충전 후 출금해야 하는 경우
        if a < 0 and kakaoMoney < -a:
            mValue = -a + b - kakaoMoney # 충전에 필요한 금액 
            if firstWithdraw:  # 처음 출금
                maxM = b # 잔액을 현재 로그의 잔액으로 설정
                res = mValue # 결괏값을 현재 로그에서 충전에 필요한 금액으로 설정
                firstWithdraw = False
            else:
                mValue = gcd(res, mValue) # res와 mValue의 최대 공약수
                maxM = max(maxM, b) # 이전에 기록한 가장 큰 잔액과 현재 로그 잔액 중 큰 값으로 업데이트

                if mValue < maxM: # 최대 공약수가 가장 큰 잔액보다 작을 경우는 최소 충전 단위가 존재하지 않는 경우에 해당한다.
                    res = -1
                else: 
                    if mValue == 1 and b != 0: # M이 1인데 로그의 잔액이 0이 아닌 경우는 M이 존재하지 않는 경우에 해당한다.
                        res = -1
                    else: # res값 mValue로 갱신
                        res = min(mValue, LIMIT)

            kakaoMoney = b # 카카오 머니의 잔액을 b로 설정
            continue
        
        # (2) 그 외의 경우에는 로그에 따라 카카오 머니 잔액에서 입금이나 출금을 했을 때 로그에 기록한 b와 일치하는지 체크
        if kakaoMoney + a != b:
            res = -1
        else:
            kakaoMoney = b

    print(res)