[백준/3955] 캔디 분배 (Python)

Problem : https://www.acmicpc.net/problem/3955

3955번: 캔디 분배

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 01:01:25

 

---

 

문제 설명

 

 

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

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

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

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

 

출력 예시

 

IMPOSSIBLE
3
872
14696943
166666655

 

 

---

 

풀이

 

우리가 구하고 싶은 값은 사야 하는 봉지의 수 X'이다. (X'은 자연수)

수식으로 나타내 보면, KX + 1 = CX', -KX + CX' = 1이 성립한다.

 

우선 특이사항인 경우를 살펴보자.

 

• K == C == 1 : 이 경우 X+1 = X' 이고, X >= 1이므로 X' >= 2이다. 따라서 2를 출력해주면 된다.
• K == 1 : 이 경우 CX' = X + 1이다. (X == X' == 1)일때 이 식이 성립하므로, 1을 출력해주면 된다. 문장으로 풀어서 쓰면, 사탕을 나누어 주는 사람 수는 한 명이므로 한 봉지만 사도 충분하다.
• C == 1 : 이 경우 KX + 1 = X'이 된다. 이 식을 가장 쉽게 만족시키는 (X, X') 쌍은 (1, K+1)이다. 따라서 K+1을 출력하면 된다. 문장으로 풀어서 쓰면, 봉지에 사탕 수가 1개밖에 없으니 사람수 + 1봉지를 사면 된다. 주의할 점은 K+1 이 최대로 살 수 있는 봉지값을 넘는지 검사해야 한다는 점이다.

 

이쯤이면 됬고, 우리는 이제 -KX + CX' = 1을 만족하는 순서쌍을 빠른 시간 내에 찾아낼 수 있어야 한다. 이를 풀기 위해서 배주 항등식과 확장 유클리드 호제법 개념을 이용하는 게 문제의 핵심이다. 공부한 내용을 정리할 겸 설명해보자.

 

임의의 정수 a, b에 대해 ax + by = gcd(a, b) 항등식에서, 이를 만족하는 정수쌍 (x, y)가 존재함과 동시에 gcd(a, b)는 ax + by 형태로 표현할 수 있는 가장 작은 자연수가 된다. 이것이 배주 항등식의 핵심이다.

 

https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

Bézout's identity - Wikipedia

 

우리는 앞서 -KX + CX' = 1이 성립함을 알고 있으므로, gcd(K, C)는 1이어야 한다. 즉 둘이 서로소가 아니라면 불가능하다.

 

두 번째로, 확장 유클리드 호제법은 이러한 배주 항등식 ax + by = gcd(a, b)꼴을 만족하는 (x, y)쌍을 찾는 알고리즘이다. 우리가 유클리드 호제법을 적용할 때를 떠올리자.

 

• a = bq + r 꼴로 나타낼 수 있고
• gcd(a, b) = gcd(b, r)임을 보일 수 있으며
• 이를 재귀적으로 r = 0일때, 즉 gcd(b', 0) = b'일때까지 적용하는 방식으로

유클리드 호제법을 적용한다.

 

이를 일반화하여, a = r0, b = r1이라고 명명하면, 이 호제법을 진행하는 n번째 과정은

 

꼴로 정리할 수 있겠다. 이제, x, y에 대해서도 이렇게 귀납적으로 정의해 보자.

 

이를 gcd값이 구해질 때까지 반복하면 최종적인 x, y의 차수를 구할 수 있다는 점이 핵심이다.

 

로 나타낸다면,

가 됨을 귀납적으로 확인할 수 있으므로 x, y를 같이 구할 수 있게 된다.

 

즉 우리가 구하고자 하는 값을 확장 유클리드 알고리즘으로 구하고, 만일 음수값이 나온다면 K값을 더해줌으로써 양수로 바꾸어 줄 수 있다. (모듈러 연산)

 

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = 10 ** 9
def extended_euclidean(a, b) :
  r1, r2 = a, b
  s1, s2 = 1, 0
  t1, t2 = 0, 1
  
  while r2 :
    q = r1 // r2
    r1, r2 = r2, r1 - q * r2
    s1, s2 = s2, s1 - q * s2
    t1, t2 = t2, t1 - q * t2
    
  return r1, s1, t1

def solve() :
  K, C = map(int, input().split())
  if K == 1 :
    print(1 if C > 1 else 2)
    return
  if C == 1 :
    print(K+1 if K < MAX else "IMPOSSIBLE")
    return
  gcd, _, ans = extended_euclidean(K, C)
  if gcd > 1 or ans > MAX:
    print("IMPOSSIBLE")
  else :
    print(ans if ans > 0 else K + ans)

for _ in range(int(input())) :
  solve()

풀이 완료!