[BOJ] 15998 카카오머니

문제 링크

 

www.acmicpc.net/problem/15998

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제를 풀기 위해서는 각각의 출금 금액을 기록해두고, 이 금액들의 최대공약수를 구해야한다. 유클리드 호제법을 사용하면 빠른 시간안에 최대공약수를 구할 수 있다.

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

입/출금액은 최대 10^18원 까지 가능하므로 long long형을 사용했다.

 

 

출금 금액에서 구한 최대공약수를 뺐을 때도 필요한 금액을 낼 수 있다면, 필요 이상으로 인출을 한 것이므로 이 경우 답이 존재하지 않는다. 

이러한 경우가 발생하지 않는다면 구한 최대공약수가 답이 된다. 또한 출금을 아예 하지 않았다면 최소 충전 단위는 아무 숫자나 가능하므로 그냥 1을 출력해준다. 단, 로그 자체에 모순이 있는 경우 (원래 남아있던 금액에서 출금액을 뺀 금액이 현재 남아있는 금액과 맞지 않는 경우)에는 -1을 출력해준다.

 

전체 코드는 아래와 같다.

#include<iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 300000; //15998 카카오머니
typedef long long ll;
int n;
ll arr[MAX][2];
vector<pair<int, ll>> vec;
vector<ll> measure;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	int i, chk=1;
	ll curMoney = 0;
	cin >> n;
	//1. 인출 금액 구하기
	for (i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
		if (arr[i][0] < 0 && -arr[i][0] > curMoney) { // 현재 금액보다 더 많은 금액을 출금하려 하는 경우
			ll km = arr[i][1] - arr[i][0] - curMoney; // 금액 m을 k번 인출했을 때의 인출 금액
			vec.emplace_back(i, km);
		}
		else if(curMoney + arr[i][0] != arr[i][1]) {
			chk = 0;
		}
		curMoney = arr[i][1];
	}
	
	if (!chk) {
		cout << -1;
		return 0;
	}
	if (vec.size()) {
		//2. 인출 금액들의 최대공약수 구하기
		ll tmp = vec[0].second;
		for (i = 1; i < vec.size(); i++) {
			if (tmp < vec[i].second) tmp = gcd(vec[i].second, tmp);
			else tmp = gcd(tmp, vec[i].second);
		}

		int chk = 1;
		for (auto it : vec) {
			int idx = it.first;
			ll prev = (idx == 0 ? 0 : arr[idx - 1][1]);
			if (it.second - tmp >= -(prev + arr[idx][0])) { // 만일 인출을 필요 이상으로 한 경우,
									// 이 값은 답이 될 수 없다.
				chk = 0;
				break;
			}
		}
		if (chk) {
			cout << tmp;
			return 0;
		}
		cout << -1;
	}
	else cout << 1;
}