[3955] 캔디 분배

문제 링크 : https://www.acmicpc.net/problem/3955

3955 - 캔디 분배

본문

창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다.

따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다.

만약 파티에 $K$명이 참가한다면, 공정하게 나누어주려면 $K\times X$개를 사야 한다. ($X$는 자연수)

선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 ($K\times X+1$)개를 구매하려고 한다.

사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 $C$개 들어있다. 문제의 조건을 만족하면서 구매할 수 있는 사탕 봉지의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. ($0<t<100$) 각 테스트 케이스는 한 줄로 이루어져 있고, $K$와 $C$가 공백으로 구분되어져서 주어진다. ($1\le K,C\le {10}^9$) 선영이는 부자가 아니기 때문에 ${10}^9$개를 넘는 사탕 봉지를 구매하지 못한다.

출력

각 테스트 케이스에 대해서 문제의 조건을 만족시키면서 구매할 수 있는 사탕 봉지가 없다면, “IMPOSSIBLE”을 출력한다. 이 경우가 아닌 경우에는 선영이가 구매해야 하는 사탕 봉지의 수를 출력한다. 만약, 가능한 봉지의 수가 여러개라면 아무거나 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

문제를 수식으로 생각해보자. 사람 수를 $K$, 봉지 하나에 들어있는 사탕 개수를 $C$라고 할 때, 문제의 조건을 만족하기 위한 수식을 만들 수 있다.

$$Kx+1=Cy$$

$\text{문제 조건상 }x\ge 1,1\le y\le {10}^9$이다. 이 수식을 조금만 정리하면 아래와 같다.

$$\begin{array}{rl}Cy-Kx& =1\end{array}$$

$\text{문제 조건상 }x\ge 1,1\le y\le {10}^9$이다.

우리는 위 조건에서 $K$와 $C$를 입력받고, 저 수식을 만족하는 $x$와 $y$를 찾아야한다. 문제의 정답은 $y$를 출력하도록 하면 된다. 입력되는 수의 범위는 10억까지 가능하다. 어떤 수가 정답으로 가능한지는 모르지만, 10억까지 가능한 수를 하나하나 대입하는 것은 불가능할 것이다.

$x$와 $y$에 대해 생각을 해보자. 일단 $x$, $y$는 둘 다 자연수다. 그리고 $K$와 $C$도 입력으로 주어지므로 고정되며, 자연수다. 고정된 $K$와 $C$에 대해, 우리는 $x$와 $y$의 값을 바꿔가며 우변을 $1$로 만들어야한다. 양동이 퍼즐이랑 비슷한 것 같다. “5L짜리 양동이와 3L짜리 양동이를 이용하여 1L를 만들어라” 같은 문제와 상황이 비슷해보인다. 생각해보니 문제를 풀어쓰면 “$K$L짜리 양동이와 $C$L짜리 양동이를 이용하여 $1$L를 만들어라” 라고도 쓸 수 있겠다. 퍼즐의 상황이 이 문제와 아예 같은 양상이다.

양동이 퍼즐은 그냥 무작정 옮겨보다보면 풀리던 문제였다. $x$와 $y$의 숫자 범위가 크지 않았기 때문이다. 다만 이 문제에서는 값의 범위가 크므로 아예 같은 방법을 사용할 수는 없다. 대신 문제 상황은 아예 같으므로 퍼즐에서 사용하던 아이디어들은 똑같이 적용할 수 있을 것이다. 가지고 있는 아이디어는 아래에 정리해두자.

• 양동이를 이용해 물을 더하고 뺄 수 있다
  • 다만 이 문제에서는 양동이를 꽉 채운다는 선택지밖에 존재하지 않는다
• 두 양동이로 만들 수 없는 용량도 있다
  • 예를 들어, 10L와 2L짜리 양동이로는 홀수의 용량을 만들 수 없다
  • 5L와 3L짜리 양동이로는 모든 용량을 만들 수 있었다

위 정보를 이용하여, 결국은 두 양동이를 이용하여 1L을 만들 수 있는가를 판단해야할 필요성이 있다는 것을 알아냈다. 그런데 하나하나 다 시도해볼 수 없으므로 특정 조건을 만들어서 바로 판단할 수 있도록 해야한다. 안되는 경우를 생각해보자. 왜 10L와 2L로는 홀수 용량을 만들 수 없었을까? 반대로 왜 5L와 3L로는 모든 용량을 만들 수 있었을까?

$K$, $C$가 모두 자연수고, $x$와 $y$도 어짜피 자연수이므로, 결과값은 항상 정수의 형태일 것이다. 만약 $K=10$, $C=2$라고 가정하면, $Kx$는 10의 배수, $Cy$는 2의 배수가 된다. 둘 다 짝수이므로, 짝수에서 짝수를 뺀다고 해서 결과값을 홀수로 만들 수는 없을 것이다. 이게 원인인 것 같은데, 예시 case 중 하나일 뿐인 이 경우만으로는 case를 일반화시킬 수는 없을 것이다. 하지만 이 경우 생각해보면, $K$와 $C$에 의해 만들 수 있는 숫자들이 모두 짝수인 것은 알 수 있다. 다시 말하면 2의 배수라는 점이다. 마찬가지로 $K=5$, $C=3$인 경우에는 모든 수를 만들 수 있었고, 다른 말로는 1의 배수는 모두 만들 수 있었다는 점이다. 한번만 더해보자. 예시로 아무 숫자나 랜덤으로 생각해보자. 이번에 랜덤으로 생성한 수는 $K=24$, $C=18$이었다. 여러번 물을 넣고 빼보면서 알아낸 것은, 이 두 양동이를 이용하여 만들 수 있는 숫자들이 6의 배수였다는 점이었다. 갑자기 규칙이 보인다. $K$와 $C$가 고정되어있는 상황에서, $y$와 $x$를 바꿔가면서 얻을 수 있는 정수들은 K와 C의 최대공약수의 배수들이라는 점이었다.즉 $K$와 $C$가 정해져있다면, 만들 수 있는 최소의 정수는 두 수의 최대공약수이며, 이 문제에서는 만들어야하는 정수가 1이므로, “두 수의 최대공약수가 1“이어야한다는 조건을 생각할 수 있다.

두 수의 최대공약수를 구하려면 사용하는 알고리즘들이 몇개 있을텐데, 그중에서 유명하게 쓰이는게 유클리드 알고리즘 일 것이다. 그런데 유클리드 알고리즘이 문제를 해결할 정보를 전부 주지는 못한다. 그런데 유클리드 알고리즘의 확장판이 있었다. 그리고 그 확장판이, 이 문제를 해결할 수 있는 실마리를 제공하고 있었다.

위에서 찾았던 조건이 ‘베주 항등식’ 이라는 명칭으로 증명이 되어있었다. 그래서, $K$와 $C$의 최대공약수가 1이 아니라면 문제에서 원하는 답을 절대 찾을 수 없다는 것을 증명할 수 있었다.

알고리즘 자체에 대한 설명은 따로 적지는 않겠다. 알고리즘의 단계를 따라가며 최대공약수를 구해보고, 최대공약수가 1이라면 $x$와 $y$의 값을 구하면 된다. 다만 문제의 조건에서 $x$가 자연수이어야한다는 점을 들어, 만약 $x$가 0 또는 음수가 나왔다면 그건 답이 아니라고 파악해야한다. 그럴 때는 좌변과 우변에 0을 더해주는 방법으로 숫자를 조절하면 된다. 좌변에 $KC-KC$를 더해주는 것이다. 그러면 수식을 아래와 같이 조절할 수 있다.

$$\begin{array}{rl}Cy-Kx& =1\\ Cy-Kx+KC-KC& =1\\ C(y+K)-K(x+C)& =1\end{array}$$

$K$와 $C$는 모두 자연수이므로, $x+C$ 또한 자연수로 변환할 수 있다. 그 때의 $y$값은 $y+K$인 점을 알 수 있다. 즉, $x$의 값이 음수 또는 0이라면, 찾은 답에서 $K$를 더해 값의 범위를 맞춰주는 작업이 필요하다. 물론 이렇게 맞춘 이후에, $y$ 자체의 정답 범위인 ${10}^9$ 이하인지를 체크해주면 된다. 그것만 하면 정답을 찾을 수 있다.

• 참고 알고리즘 : 확장 유클리드 알고리즘

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 12

#include <stdio.h>

typedef long long ll;

#define MAX_CNT (ll)(1e9)

void EEA(ll a, ll b) {
    ll r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
    ll r, s, t, q;

    while (r2 != 0) {
        q = r1 / r2;

        r = r1 % r2;
        r1 = r2, r2 = r;

        s = s1 - q * s2;
        s1 = s2, s2 = s;

        t = t1 - q * t2;
        t1 = t2, t2 = t;
    }
    s = s1, t = t1;

    if (r1 != 1) {
        printf("IMPOSSIBLE\n");
    } else {
        if (s >= 0) {
            t += a;
        }

#define STD (ll)(1e9)
        if (t > STD) {
            printf("IMPOSSIBLE\n");
        } else {
            printf("%lld\n", t);
        }
    }

    return;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        EEA(a, b);
    }
    return 0;
}