3955 - 캔디 분배
본문
창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다.
따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다.
만약 파티에 $K$명이 참가한다면, 공정하게 나누어주려면 $K \times X$개를 사야 한다. ($X$는 자연수)
선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 ($K \times X + 1$)개를 구매하려고 한다.
사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 $C$개 들어있다. 문제의 조건을 만족하면서 구매할 수 있는 사탕 봉지의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. ($0 < t < 100$) 각 테스트 케이스는 한 줄로 이루어져 있고, $K$와 $C$가 공백으로 구분되어져서 주어진다. ($1 \leq K, C \leq 10^9$) 선영이는 부자가 아니기 때문에 $10^9$개를 넘는 사탕 봉지를 구매하지 못한다.
출력
각 테스트 케이스에 대해서 문제의 조건을 만족시키면서 구매할 수 있는 사탕 봉지가 없다면, “IMPOSSIBLE”을 출력한다. 이 경우가 아닌 경우에는 선영이가 구매해야 하는 사탕 봉지의 수를 출력한다. 만약, 가능한 봉지의 수가 여러개라면 아무거나 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 128MB |
풀이
문제를 수식으로 생각해보자. 사람 수를 $K$, 봉지 하나에 들어있는 사탕 개수를 $C$라고 할 때, 문제의 조건을 만족하기 위한 수식을 만들 수 있다.
\[Kx + 1 = Cy\]$\text{문제 조건상 } x \geq 1, 1 \leq y \leq 10^9$이다. 이 수식을 조금만 정리하면 아래와 같다.
\[\begin{align} Cy - Kx &= 1 \end{align}\]$\text{문제 조건상 } x \geq 1, 1 \leq y \leq 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{align} Cy - Kx &= 1 \\ Cy - Kx + KC - KC &= 1\\ C(y + K) - K(x + C) &= 1 \end{align}\]$K$와 $C$는 모두 자연수이므로, $x+C$ 또한 자연수로 변환할 수 있다. 그 때의 $y$값은 $y + K$인 점을 알 수 있다. 즉, $x$의 값이 음수 또는 0이라면, 찾은 답에서 $K$를 더해 값의 범위를 맞춰주는 작업이 필요하다. 물론 이렇게 맞춘 이후에, $y$ 자체의 정답 범위인 $10^9$ 이하인지를 체크해주면 된다. 그것만 하면 정답을 찾을 수 있다.
- 참고 알고리즘 : 확장 유클리드 알고리즘
코드
사용 언어 : C
최종 수정일 : 2023 / 3 / 12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}