[BOJ 15998] 카카오머니

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

15998번: 카카오머니

 

- 문제 요약

 

카카오페이는 카카오톡을 통해 송금, 결제 등을 할 수 있는 핀테크 서비스이다.

처음에 무지의 카카오머니 잔액은 0원이다.

이 문제에서는 입금 또는 출금할 때 액수가 1원 단위여야 한다는 것 외의 별다른 제약이 없다고 가정하자.

즉, 실제 카카오머니의 제약사항인 잔액 200만 원 이하, 송금은 1일에 50만 원 한도 등은 무시한다.

x 원이 입금될 경우, 무지의 카카오머니 잔액은 x 원만큼 증가한다.

그러나, x 원을 출금할 때는 상황이 다르다.

만약 잔액이 x 원 이상이라면, 잔액에서 x 원을 차감하면 된다.

그러나, 잔액이 x 원 미만이라면 연결된 통장에서 돈을 가져올 필요가 있다.

카카오는 이를 위해 최소 충전 단위 M(양의 정수)을 두어서, 잔액이 x 원 이상이 되기 전까지 M 원을 통장에서 가져오다가, 잔액이 x 원 이상이 되면 x 원을 잔액에서 차감한다.

무지는 카카오머니를 이용하기 시작할 때부터 자신만의 입출금 로그를 작성하였다.

이 로그는 N 개의 두 정수 쌍 (ai, bi)로 이루어져 있으며, 시간 순서대로 저장되어 있다.

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

무지는 자신이 작성한 로그에 모순이 없는지를 점검해 보고자 한다.

무지가 생각한 방법은, 입출금 로그만 보고 유효한, 즉 로그에 모순이 생기지 않도록 하는 최소 충전 단위 M 이 존재하는지, 존재한다면 값이 얼마인지 확인하는 것이다.

무지를 도와, 이 일을 대신해 줄 프로그램을 작성하라.

만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 10^18)이 존재한다면, 첫 번째 줄에 M 을 출력한다.

가능한 값이 여러 가지 있다면, 그중 9 * 10^18 이하인 것을 아무거나 하나 출력한다.

존재하지 않는다면 -1을 출력한다.

 

 

- 알고리즘 정리

 

입금은 따로 고려할 상황이 존재하지 않습니다.

현재 출력을 해야 하는 상황인 경우, 충전에 필요한 최대 금액의 최소 공배수를 구해줍니다.

구한 값을 M으로 설정한 후, 로그의 모순 여부를 따져주면 풀 수 있는 문제입니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MAX=(9*(pow(10,18)));

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,money=0,mx=0,result=1;
	bool flag=true;
	cin>>n;
	ll a,b;
	while(n--){
		cin>>a>>b;
		if(result==-1){
			continue;
		}
		if(a<0&&money<-a){
            ll mxvalue=-a+b-money;
            if(flag){
            	mx=b;
            	result=mxvalue;
            	flag=false;
			}
			else{
				mxvalue=gcd(result,mxvalue);
				mx=max(mx,b);
				if(mxvalue<mx){
					result=-1;
				}
				else{
					if(mxvalue==1&&b!=0){
						result=-1;
					}
					else{
						result=min(mxvalue,MAX);
					}
				}
			}
			money=b;
			continue;
		}
		if(money+a!=b){
			result=-1;
		}
		else{
			money=b;
		}
	}
	cout<<result;
}

코드 제출 결과