코드 복사/붙여넣기 하는 당신이 아름답습니다.

15998 : 카카오머니

풀이

주어지는 입력을 a[i], b[i]라고 하자.

b[i]-b[i-1] == a[i]인 경우는 돈을 뽑아서 쓰지 않는 정상적인(?) 경우이다.

b[i]-b[i-1] != a[i]인 경우는 비정상적인(?) 경우이다.

여기서 비정상적인(?) 경우도 두 경우로 나뉜다.

하나는 인출하지 않는 상황에서 남은 금액이 맞지 않는 경우, 이건 그냥 짜주자.

인출하는 경우에, 은행에서 인출하는 금액 kb[i]-b[i-1]-a[i]이다.

오 그렇다면 이러한 k가 여러개 있을 수 있는데,

우리가 구하는 건 공통된 k이므로 이러한 k들의 gcd를 구해주자.

그러한 gcd 값을 gcd_k라고 하자.

그럼 답이 모순되는 경우는 어떤 경우일까?

만약 비정상적인(?) ib[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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-17 12:22

Read more posts by this author