백준 15998 카카오머니

카카오 코드 페스티벌 2018 본선 문제

 

 입출금 로그를 보고 잘못된 부분이 있는지, 없다면 최소 충전금액은 얼마인지 알아내는 문제이다.

 

풀이과정

 먼저, a, b를 list로 가지고 있을 필요없이 입력받고 바로바로 처리하면 효율적으로 문제를 해결할 수 있다.

 minB는 0이 아닌 b의 최솟값이며, lastB는 이전 step의 b값이 된다.

 a+lastB가 음수인 경우에는 충전이 필요하며 충전 금액 temp는 아래와 같이 주어진다.

 temp = b - a - lastB

 충전금액은 최소충전금액의 배수만 가능하므로, 최소충전금액(변수 pay)은 충전액들의 최소 공배수가 되고, 이를 해결하기 위해 pay 변수를 계속해서 pay변수와 위의 temp 변수의 최대공약수로 갱신해준다.

 

 로그가 잘못 되었을 조건은 아래와 같다.

 1. 각 step에서 잔액 b는 전 step에서의 잔액과 현 step에서의 입출금 a의 합으로 주어져야하는데, b = lastB + a 를 만족하지 않으면 그 로그는 잘못된 로그이다.

 2. 최소충전금액이 pay이므로, 입출금 후의 잔액의 최솟값 minB는 pay보다 작아질 수 없다. 따라서 minB < pay 인 경우 그 로그는 잘못된 로그이다.

 

Python Code

import sys
 
def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)
 
n = int(input())
minB = pow(10,18)
last_b = 0
pay = None
 
valid = True
for i in range(n):
    a,b = map(int,sys.stdin.readline().split())
    if a+lastB<0:
        temp = b-a-lastB
        if b != 0 and b<minB : minB=b
        if pay == None:
            pay = temp
        else :
            pay = gcd(pay,temp)
            if pay <= minB and minB != pow(10,18):
                valid = False
                break
    else:
        if lastB + a != b:
            valid = False
            break
    lastB = b
if valid and pay != None : print(pay)
elif valid and pay == None : print(1)
else : print(-1)

문제풀기

15998번: 카카오머니