[BOJ] 백준 3955번 캔디 분배 (Java)

#3955 캔디 분배

난이도 : 플레 5

유형 : 정수론 / 확장 유클리드 호재법 

3955번: 캔디 분배

▸ 문제

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

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

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

ax + by = 1 인 해를 구해야 한다. 이는 두 정수 사이의 최대 공약수를 구하는 유클리드 호재법 GCD(A,B)=GCD(B,r)에서 확장된 유클리드 호재법을 사용하여 풀이를 할 수 있다. 아래의 증명 과정은 해당 블로그를 참고했다.

 

유클리드 호재법 증명

두 정수 A,B(A>B)A,B(A>B) 의 최대공약수(GCD)를 GG 라고 하자. GG 는 공약수이므로 두 서로소 a,ba,b 에 대해 다음 식이 성립한다.

 

  A=aG, B=bG

 

A 를 B 로 나눈 나머지를 r , 몫을 q 라고 하면 A=qB+r (0≤r<|B|)를 만족한다. 이 식과 위의 식을 이용해서 새로운 식을 전개해보면 다음과 같다.

 

aG=bGq+r, r=G(a−qb)

 

이 때 B 와 r 의 최대공약수가 G 임을 보이면 증명하면 된다. 이는 b 와 a−qb가 서로소임을 증명하는 것과 같다. G = B/b이므로 r = B(a-qb)/b로 표현할 수 있기 때문이다.

 

귀류법을 사용하여 b 와 a−qb 가 서로소가 아니라고 가정해보자. 서로소가 아닐 경우 2이상의 최대공약수가 존재하며 그걸 p 라고 하면 두 정수 n,m에 대하여 다음 식이 성립한다.

 

 b=np, a−qb=mp

 

a−qb=mp 는 다시 b=np 를 이용해 아래와 같이 전개할 수 있다.

 

a=qb+mp

    =qnp+mp

     =(qn+m)p

 

위 식에 의해서 a,b는 공약수인 p 를 가지게 되는데 가장 처음에 가정했던 a,b 가 서로소라는 것에 모순이 되기 때문에 b,a−qb 는 반드시 서로소여야 한다. 따라서 GCD(B,r)=G 가 성립한다.

 

확장 유클리드 호제법(Extended Euclidean Algorithm)

베주 항등식에 따라서 GCD(a,b)=d 라고 할 때 ax+by=d 를 만족하는 x,y 가 존재하며 이는 유클리드 호제법의 과정을 역으로 따라가면 찾을 수 있다. 따라서, 유클리드 호제법의 과정을 따라가봐야 한다. 두 정수 a,b 에 대해 나눗셈 정리와 유클리드 호제법을 반복하여 다음과 같이 나열할 수 있다.

 

a = b*q(0) + r(1)

b = r(1)*q(1) + r(2)

r(1) = r(2)*q(2) + r(3)

...

r(i−1) = r(i)*q(i) + r(i+1)

 

여기서 r(i+1) = r(i−1) − r(i)*q(i) 를 얻을 수 있고 r(i+1) = 0 일 때 알고리즘이 종료된다는 것을 알 수 있다. 여기서 d 는 r(i) 이므로 ax+by 꼴로 나타내기 위해서 r(0) = a, r(1) = b 라고 하면 r(0) = a*1+b*0 이 되고 r(1) = a*0+b*1 이 된다.  이는 이후의 r(i) 도 같은 꼴로 나타내어진다는 것을 알 수 있다. 이 때 임의의 r(i) 에 대해 a 의 계수를 s(i),  b의 계수를 t(i) 라고 하면 아래와 같이 표현할 수 있다.

 

r(i)=s(i)*a + t(i)*b

 

이를 r(i+1) = r(i−1) − r(i)*q(i) 에 대입하면 다음 점화식을 얻어낼 수 있다.

 

s(i+1)*a + t(i+1)*b = (s(i−1)*a + t(i−1)*b) − (s(i)*a + t(i)*b)*q(i)

                                       = s(i−1)*a − s(i)*a*q(i) + t(i−1)*b − t(i)*b*q(i)

                                    = (s(i−1) − s(i)*q(i))*a + (t(i−1) − t(i)*q(i))*b

 

즉, r(i+1) = ax + by의 형태로 다시 표현이 가능해졌다.

x = s(i-1) - s(i)*q(i)

y = t(i-1) - t(i)*q(i)

 

풀이

문제에서는 GCD(a,b)=d 라고 할 때 ax+by=d 라고 만족하는 식을 구하면 된다. 그런데 d = 1인 값을 주어졌으므로 ax + by = 1이 되는 x와 y를 구하면 된다.

 

1. a = 10, b = 7

10*x + b*y = 1인 식을 구하기 위해 r = 1이 될 때까지 확장된 유클리드 호제법의 식을 사용한다. 그러면 다음과 같은 값이 주어진다.

 

s = -2, t = 3

 

ax + by = 10* 2 + 7*3 = 1이므로 성립됨을 확인할 수 있다. 따라서 답은 3이다.

 

 

2. a= 1337, b = 23

1337*x + 23*y = 1인 식을 구하기 위해 r = 1이 될 때까지 확장된 유클리드 호제법의 식을 사용한다. 그러면 다음과 같은 값이 주어진다.

 

s = 8, t = -465

 

1337*8 + 23*-465 = 1이다. 그런데 우리는 a명에게 b개의 개수로 캔디를 나눠줘야 하기 때문에 t의 값이 양수이고 a = 1337보다 작거나 같아야 한다. 

 

그래서 식을 좀 바꿔서 -465 값에 a를 더해주면 872가 되고 이에 대한 식을 다시 구하면  1337*-15 + 23*872 = 1로 표현이 가능하다.

 

마지막으로 구해진 값이 다음과 같은데 결론적으로 x = s(i-1)+s(i), y =t(i-1) + t(i)임을 알 수 있다. 이 부분에 대해서는 나도 완벽히 이해하질 못했다. 

• s0 :8, s1 :-23
• t0 :-465, t1 :1337

 

따라서 답은 872이다.

 

풀이 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		while(t-->0){
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			long[] res = eeg(k,c);
			if(res[1] != 1) { // 나머지가 1이 아니라면 impossible
				System.out.println("IMPOSSIBLE");
			}else {
				long t0 = res[0];
				
				// t0 = (t0 % k + k ) % k 
				// 이는 
				// t0 % = k;
				// if(t0 < 0) t0 += k;와 같은 값 
				t0 = (t0% k + k) % k;
                t0 = Math.max(t0, (k+c)/c);
				
				if(t0 <= 1e9) {
					System.out.println(t0);
				}else { // 10^9보다 크면 impossbile
					System.out.println("IMPOSSIBLE");
				}
			}
		}
	}
	
	static long[] eeg(long a, long b) {
		long r0 = a, r1 = b;
		long s0 = 1, s1 = 0;
		long t0 = 0, t1 = 1;
		
		long tmp;
		while(r1 != 0) {
			long q = r0/r1;
			
			tmp = r0 - q*r1;
			r0 = r1;
			r1 = tmp;
			
			tmp = s0 - q*s1;
			s0 = s1;
			s1 = tmp;
			
			tmp = t0 - q*t1;
			t0 = t1;
			t1 = tmp;
		}
		
		return new long[] {t0, r0};
		
	}
}