[코테] 백준 3955번 : 캔디 분배 (java)

 

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

알고리즘 분류 : 수학, 정수론, 확장 유클리드 호제법

❓문제

---

🔅해석

확장 유클리드 호제법 알고리즘을 이용한다. (공식 : ax+by=gcd(a,b))

방정식에 적용할 a, b, c를 생각해보자면, a와 b는 입력값인 인원수, 한 봉지에 든 사탕 개수로 둘 수 있다.

a	x	b	y
인원수	인당 나눠줄 사탕 수	한 봉지에 든 사탕 수	사탕 봉지수

ax + 1 = by 

아래와 같이 항 정리를 한다.

-ax + by = 1

 

여기서 주의할 점은, 나머지 정의가 0 < r < a 인데 -a이면 처리가 불가능해진다. 

그래서 a, b에 음수가 들어오지 않도록 x가 음수 값을 가지게 한다.

a(-x) + by = 1

 

이제 확장 유클리드 호제법을 통해 s, t, r 값을 구한다.

public static EGResult egcd(long a, long b) {
		long s0 = 1, t0 = 0, r0 = a; // 마지막 s,t,r이 될 것임
		long s1 = 0, t1 = 1, r1 = b;

		long temp;
		// b기준이었으나 현재 b는 r1
		while (r1 != 0) {
			long q = r0 / r1;

			temp = r0 - r1 * q; // 새로운 나머지
			r0 = r1;
			r1 = temp;

			temp = s0 - s1 * q;
			s0 = s1;
			s1 = temp;

			temp = t0 - t1 * q;
			t0 = t1;
			t1 = temp;
		}

		return new EGResult(s0, t0, r0);
	}

 

 

Ax + By = C 일 때, C % D == 0이면, 해가 존재한다는 베주 항등식 특성을 통해 해의 여부를 판단한다.

if (result.r != 1)

 

 

초기해를 구한다.

// 초기해
// x0 = s * C / D
// y0 = t * C / D
long x0 = result.s;
long y0 = result.t;

 

 

초기해가 조건에 의해 답이 안될 수 있으므로 일반해의 공식을 이용한다.

x = x0 + B * k

y = y0 - A / D * k

 

(해당 문제에서 D는 1이므로 생략한다)

조건 1. x (= 인당 나눠줄 사탕 수) > 0

다만, 위에서 a가 음수 값을 가지는 것을 피하기 위해 x에 마이너스를 해줬으므로 위 조건에도 적용을 한다.

x < 0

x0 + B * k < 0  (일반해의 공식 적용)

 

조건 2. 0 < y(= 사탕 봉지수 ) <= 1e9(10의 9승)

0 < y0 - A * k <= 1e9  (일반해의 공식 적용)

 

조건 2개의 식을 k 기준으로 바꿔주면 k의 경계값이 답이 된다.

조건 1. k < -x0 / B

조건 2. (y0 - 1e9) / A <= k < y0 / A 

 

위 조건을 코드로 바꾸면 아래와 같다.

long kFromY = (long) Math.ceil((double) y0 / (double) A) - 1;
long kFromX = (long) Math.ceil((double) -x0 / (double) B) - 1;

long k = Math.min(kFromY, kFromX);

// (y0 - 1e9) / A <= k
long kLimitFromY = (long) Math.ceil((y0 - 1e9) / (double) A);

if (kLimitFromY <= k) {
    // k에 대한 y 출력
    sb.append(y0 - A * k).append("\n");
} else {
    // 해가 없음
    sb.append("IMPOSSIBLE").append("\n");
}

 

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, A, B;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		StringTokenizer st;
		for (int i = 0; i < N; i++) {

			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());

			EGResult result = egcd(A, B);
            
			if (result.r != 1) {
				// 해가 없음
				sb.append("IMPOSSIBLE").append("\n");
			} else {
				// 초기해
				long x0 = result.s;
				long y0 = result.t;

				// 초기해가 답이 안 될 수 있음
				// 일반해의 공식 (공식을 외우지 않아도 유추 가능함)
				// x = x0 + B * k
				// y = y0 - A / D * k
                
				// k < -x0 / B //k기준으로 바꿈
				// (y0 - 1e9) / A <= k < y0 / A //k기준으로 바꿈
				//
				// (y0 - 1e9) / A <= k < y0 / A //나누기하고 소수점 버리면 안됨. (equal이 있으면 버리고 없으면 소수점 버리면
				// 안됨, 계산한 값을 올림하고 -1를 하면 최대 정수가 나옴)
                
				long kFromY = (long) Math.ceil((double) y0 / (double) A) - 1;
				long kFromX = (long) Math.ceil((double) -x0 / (double) B) - 1;

				long k = Math.min(kFromY, kFromX);

				long kLimitFromY = (long) Math.ceil((y0 - 1e9) / (double) A);

				if (kLimitFromY <= k) {
					// k에 대한 y 출력
					sb.append(y0 - A * k).append("\n");
				} else {
					// 해가 없음
					sb.append("IMPOSSIBLE").append("\n");
				}
			}
		}

		System.out.println(sb.toString());
		br.close();
	}

	public static EGResult egcd(long a, long b) {
		long s0 = 1, t0 = 0, r0 = a; // 마지막 s,t,r이 될 것임
		long s1 = 0, t1 = 1, r1 = b;

		long temp;
		// b기준이었으나 현재 b는 r1
		while (r1 != 0) {
			long q = r0 / r1;

			temp = r0 - r1 * q; // 새로운 나머지
			r0 = r1;
			r1 = temp;

			temp = s0 - s1 * q;
			s0 = s1;
			s1 = temp;

			temp = t0 - t1 * q;
			t0 = t1;
			t1 = temp;
		}
		return new EGResult(s0, t0, r0);
	}
}

class EGResult {
	long s;
	long t;
	long r;

	public EGResult(long s, long t, long r) {
		super();
		this.s = s;
		this.t = t;
		this.r = r;
	}

}

 

---

❗결과