[APS] 백준 15998. 카카오머니 C++ 풀이 (최대공약수, GCD, 유클리드 알고리즘)

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

15998번: 카카오머니

 

 

 Problem 

1. 처음 카카오머니의 잔액은 0원이다. 무지는 10^100원인 자신의 통장과 카카오머니 계정을 연결했고, 입금 또는 출금을 할 수 있다.
2. 이 때, 충전의 단위는 최소 충전 금액 M이다. 출금 시 잔액이 부족하면 연결된 통장에서 돈을 입금(충전)해야하는데, 카카오머니 잔액이 사용하려는 금액 이상이 될 때 까지 통장에서 M원을 가져온다.
3. 두 정수 쌍 (ai, bi)로 이루어진 로그가 N(1 ≤ N ≤ 300,000)개 주어진다.
4. ai = 0인 경우는 없으며, ai > 0이라면, 무지의 카카오머니에 ai 원이 입금되었고, 입금 결과, 잔액은 bi 원이라는 뜻이다. ai < 0이라면, 무지의 카카오머니에서 -ai 원이 출금되었고, 출금 결과, 최종적으로 잔액은 bi 원이라는 뜻이다.
5. 로그에 모순이 생기지 않도록 하는 최소 충전 단위 M이 존재하는지, 존재한다면 값이 얼마인지 출력한다.

 

 

 Solution 

역대급으로 뻘짓을 많이 한 문제 같습니다. 처음에 문제 보고 바로 이런 식으로 풀면 되겠다! 싶었어서 이렇게 오래 걸릴 줄 몰랐는데.. 제가 간과한 부분은 아래와 같습니다.

[1] 입력으로 옳은 로그만 들어오는 것은 아니다. 따라서, 로그의 유효성 여부도 판별 해야한다.
[2] 필요 이상으로 충전했는지 여부를 확인하기 위해 최소 잔액을 두고 충전하는 경우만 갱신해야 한다.

위의 두 가지 경우를 잘 고려한다면 각 조건별로 나눠서 문제에서 시키는 대로만 하면 됩니다.

문제를 읽으면서 눈치 챌 수 있겠지만, 최대공약수를 이용하는 문제입니다. 기존의 최소 충전 금액과 새로운 최소 충전 금액 사이의 최대공약수가 최종 M이 되기 때문입니다. 최대공약수는 GCD(Greatest Common Denominator)라고 하며, 최대공약수를 구하는 알고리즘을 유클리드 알고리즘이라고 합니다. 최대공약수는 아래 방식으로 쉽게 구현할 수 있습니다.

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

재귀는 때에 따라 부하가 발생할 수도 있으므로, 단순 반복문으로도 가능합니다.

int gcd(int a, int b) {
    int tmp;
    
    // b가 a보다 크다면 바꾼다.
    if (a < b) {
    	tmp = a;
    	a = b;
    	b = tmp;
    }
    
    while (b) {
    	tmp = a % b;
    	a = b;
        b = tmp;
    }
    return a;
}

최대공약수를 만들 수 있으니, 이제 문제를 풀어봅시다.

먼저, 로그는 시간 순대로 들어오기 때문에 굳이 행렬을 선언해서 입력을 받을 필요가 없습니다. 따라서, 매 라인마다 주어지는 a, b 값만 받아도 됩니다. 저는 로그의 순서쌍을 a, b, 이전 잔액을 prev, 최소 잔액을 minB라고 두었습니다. 이때, minB의 초기값은 최댓값인 10^18입니다. 또한 a < 0인 경우, 충전하는 금액을 recharge로 두었습니다.

문제에서 주는 조건 그대로 a를 기준으로 조건을 따져보겠습니다.

1. a > 0인 경우 (입금)
   충전한 금액만큼 잔액이 늘었는지 확인하는 경우 말고는 없습니다.
   따라서, prev + a != b인 경우 바로 -1을 출력하고 끝내면 됩니다.
   
   
2. a < 0인 경우 (사용, 잔액 부족 시 충전)
   남은 카카오머니 잔액에 따라 돈을 충전하지 않아도 되는 경우와 반드시 해야하는 경우가 있습니다.
   이는 prev + a가 양수인지 음수인지에 따라 결정됩니다. (양수라면 전자, 음수라면 후자)
   또한, 충전한 금액 recharge를 계산해보면 b - prev - a인 것을 알 수 있습니다. 
   
   2-1) 충전할 필요가 없는 경우, 충전하면 안됩니다.
         따라서, 0 <= prev + a일 때, recharge는 0이어야 합니다.
   2-2) 충전해야하는 경우, 충전을 안하면 안됩니다.
         따라서, prev + a < 0일 때, recharge가 양수여야 합니다.

그리고 2-2)인 경우, 충전을 했기 때문에 최소 충전 금액 M과 최소 잔액 minB를 갱신해주어야 합니다.

M은 현재 충전 금액(recharge)와 자기 자신(M)의 최대공약수로 갱신되고, minB는 b가 0이 아닐 때만 b의 최솟값으로 갱신됩니다. b가 0인 경우는 돈을 딱 맞게 다 썼다는 뜻이므로 충전한 것이 아니기 때문에 제외해야 합니다. 이때, 최소 잔액을 뜻하는 minB는 왜 필요한 걸까요?

잘 생각해봅시다. 문제에서도 주어지지만 충전은 사용하려는 금액에 맞춰서 충전됩니다. 따라서, 필요 이상으로 충전하면 안됩니다. (예를 들어, 잔액이 0원인 상태에서 최소 충전 금액이 500원인 경우를 생각해봅시다. 200원을 사용한다고 했을 때, 1번만 충전하면 되겠죠? 굳이 2번 충전해서 잔액을 800원으로 만들면 안된다는 뜻입니다.) M <= minB인 경우, 필요 이상으로 충전되었다는 뜻입니다.

또한 앞서 말했듯이, b가 0인 경우 minB는 갱신되지 않습니다. 그러나 주어지는 예제 2번에서 최소 충전 금액이 1원일 때, 남는 금액이 없어야, 즉 b가 0이어야 문제의 조건을 만족합니다. 이 경우는 minB로 처리되지 않기 때문에 M == 1인 경우 b를 확인해주어야 합니다.

여기까지입니다! 지식이 많이 필요한 문제는 아닌데 로그가 유효하지 않은 조건을 하나하나 생각하는 것이 조금 어려웠습니다 ㅠ_ㅠ 전체 풀이 코드는 아래를 참고해주세요 :) 감사합니다.

 

 

 Code