[백준 알고리즘] 3955번: 캔디 분배_Java

[문제]

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

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

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

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

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

 

[입력]

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

 

[출력]

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

 

[예제]

---

>문제 풀이

창영이는 사탕을 좋아한다.

선영이는 구매하기 전에 고민을 시작했다.

만약, K명이 참가한다면, 공정하게 K x X(자연수) 사야한다.

항상 한 아이는 사탕을 잃어버린다.

그래서 (K x X + 1) 개를 구매해야한다.

사탕은 봉지 단위로 판매한다.

사탕은 총 C개 들어있다.

몇 봉지를 사야하는가?

​

input))

t     //(0<t<100)

K C  //(1<=K, C<=10^9)

​

output))

만족하는 사탕 봉지가 없다면, "IMPOSSIBLE"

여러개면 아무거나 출력

​

즉, K와 C가 주어지고 x: 인당 나눠줄 사탕 개수, y: 구매할 사탕 봉지 개수 라고 할때,

-Kx+Cy=1 을 만족하는 y를 찾아야한다.

​

* X의 시작점은 K/C의 올림수=> (int)(K+1)/C

​

>문제 풀이

gcd를 구할 때 유클리드 호제법을 쓴다면, 일차방정식의 해를 구할 때는 확장된 유클리드 호제법을 사용할 수 있다.

​

​

확장된 유클리드 호제법 설명 참고: https://sexycoder.tistory.com/65

유클리드 호제법과 그 확장에 대한 증명

 

>전체 코드

 

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		int N, K, C;
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		for(int i=0; i<N; i++) {
			K= scan.nextInt();
			C= scan.nextInt();
			long x0, y0;
			
			EGResult result= extendedGcd(K, C);
			if(result.r!=1) {
				System.out.println("IMPOSSIBLE");
			}else {
				x0= result.s;
				y0= result.t;
				
				y0%=K;
				if(y0<0) y0+=K;
				y0= Math.max(y0, (K+C)/C);
				if(y0<= 1e9) {
					System.out.println(y0);
				}else {
					System.out.println("IMPOSSIBLE");
				}
			}
		}
	}//main

	public static EGResult extendedGcd(long a, long b) {
		long s0=1, t0=0, r0=a;
		long s1=0, t1=1, r1=b;
		
		long temp;
		while(r1!=0) {
			long q= r0/r1;
			
			temp= r0 - q*r1;
			r0= r1;
			r1= temp;
			
			temp= s0 - q*s1;
			s0= s1;
			s1= temp;
			
			temp= t0 - q*t1;
			t0= t1;
			t1= temp;
		}
		return new EGResult(s0, t0, r0);
	}//EGResult
	
	static class EGResult{
		long s, t, r;
		public EGResult(long s, long t, long r) {
			super();
			this.s= s;
			this.t= t;
			this.r= r;
		}
	}//EGResult
}

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

3955번: 캔디 분배