풀이
주어지는 입력을 a[i], b[i]라고 하자.
b[i]-b[i-1] == a[i]인 경우는 돈을 뽑아서 쓰지 않는 정상적인(?) 경우이다.
b[i]-b[i-1] != a[i]인 경우는 비정상적인(?) 경우이다.
여기서 비정상적인(?) 경우도 두 경우로 나뉜다.
하나는 인출하지 않는 상황에서 남은 금액이 맞지 않는 경우, 이건 그냥 짜주자.
인출하는 경우에, 은행에서 인출하는 금액 k는 b[i]-b[i-1]-a[i]이다.
오 그렇다면 이러한 k가 여러개 있을 수 있는데,
우리가 구하는 건 공통된 k이므로 이러한 k들의 gcd를 구해주자.
그러한 gcd 값을 gcd_k라고 하자.
그럼 답이 모순되는 경우는 어떤 경우일까?
만약 비정상적인(?) i의 b[i]가 gcd_k보다 크거나 같다면
애초에 돈을 인출할 필요가 없었던 경우이므로 이는 모순이 된다.
끙 한국말 너무 어렵다
아무튼 그렇다.
코드
#include <cstdio>
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int n;
ll res, a[300003], b[300003];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &a[i], &b[i]);
res = gcd(res, b[i]-b[i-1]-a[i]);
}
for (int i = 1; i <= n; i++) {
if (b[i]-b[i-1] == a[i]) continue;
if (res&&res<=b[i] || a[i]>0 || a[i]<0&&-a[i]<b[i-1]) return !puts("-1");
}
printf("%lld\n", res ? res : 1);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이