[BOJ 백준] 캔디 분배(3955) C++, Java

 

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

3955번: 캔디 분배

 

문제 설명 : 

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

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

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

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

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

 

입력 : 

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

출력 : 

m개의 줄에 각 사람들의 이야기에 대한 답을 출력한다. 참일 경우에는 true를, 가능할 경우에는 maybe를, 불가능한 경우에는 false를 출력한다.

 

예제 입력 : 

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

예제 출력 : 

IMPOSSIBLE
3
872
14696943
166666655

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

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

// 캔디 분배 3955
public class Main {

	// 출력용 변수
	static StringBuilder sb = new StringBuilder();

	static int t, K, C;
	static long ans;
	
	static final int INFINITE_NUMBER = 1_000_000_000;
		

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		t = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= t; tc++) {
			st = new StringTokenizer(br.readLine());
			K = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			
			// 1. 예외조건 - GCD(C, K) 는 반드시 1이다
			if (gcd(C, K) != 1) {
				sb.append("IMPOSSIBLE\n");
				continue;
			}

			// 2. 확장유클리드호제법
			ans = modInv(C, K);
			while (C * ans <= K) {
				ans += K;
			}

			// 3. 정답 출력
			if (ans > INFINITE_NUMBER) {
				sb.append("IMPOSSIBLE\n");
			}
			else {
				sb.append(ans+"\n");
			}
		}
			
		// 3. 출력
		System.out.println(sb.toString());
		br.close();
	}
	
	// 유클리드 호제법 - 최소공약수
	static int gcd(int a, int b) {
		int r;
		while ( b != 0 ) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

	// 확장유클리드 호제법
	// ax + by = gcd(a,b) 가 되는 x, y 를 구함
	static int[ ] extendedGcd(int a, int b) {
		ArrayList<Integer> s = new ArrayList<Integer>() {{ add(1); add(0); }};
		ArrayList<Integer> t = new ArrayList<Integer>() {{ add(0); add(1); }};
		ArrayList<Integer> r = new ArrayList<Integer>() {{ add(a); add(b); }};
		ArrayList<Integer> q = new ArrayList<Integer>();
		
		while (true) {
			int r2 = r.get(r.size()-2);
			int r1 = r.get(r.size()-1);
			q.add(r2 / r1);
			r.add(r2 % r1);

			if (r.get(r.size() - 1) == 0) {
				break;
			}

			int s2 = s.get(s.size() - 2);
			int s1 = s.get(s.size() - 1);

			int t2 = t.get(t.size() - 2);
			int t1 = t.get(t.size() - 1);

			int q1 = q.get(q.size() - 1);
			s.add(s2 - s1 * q1);
			t.add(t2 - t1 * q1);
		}

		// { x, y }
		int [] ret = { s.get(s.size() - 1), t.get(t.size() - 1) };

		return ret;
	}


	// ax = 1 (mod M) 을 만족하는 x / gcd(x,M)=1 일때만 해가 있다.
	static long modInv(int a, int M) {
		long result = extendedGcd(a, M)[0] + M;
		result %= M;
		return result;
	}

	
}

 

C++ 코드 : 

// 캔디 분배 3955
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

#define MAX (1000000000+3)

using namespace std;

typedef pair<int, int> pii;


// CX - KY = 1 
// (봉지당 사탕 수 C * 사탕봉지 수 ans)  = (사람수K) * (인당 사탕수X) + 1 (여유분)
// CX = 1 (modK) 
// C와 K의 gcd가 1이 아니면 찾을 수 없다
// Cx > K
int t, K, C;	// t : 테스트케이스 개수, K : 파티에 K명 참가, C : 사탕 개수

long long ans;

int gcd(int a, int b) {
	// a > b가 되도록 swap(a,b)
	if (b > a) {
		int tmp = b;
		b = a;
		a = tmp;
	}

	// 유클리드 호제법
	int c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}


// 확장유클리드 호제법
// ax + by = gcd(a,b) 가 되는 x, y 를 구함
pii extendedGcd(int a, int b) {
	vector<int> s = { 1,0 };
	vector<int> t = { 0,1 };
	vector<int> r = { a, b };
	vector<int> q;

	while (1) {
		int r2 = r[r.size() - 2];
		int r1 = r[r.size() - 1];
		q.push_back(r2 / r1);
		r.push_back(r2 % r1);

		if (r[r.size() - 1] == 0) {
			break;
		}

		int s2 = s[s.size() - 2];
		int s1 = s[s.size() - 1];

		int t2 = t[t.size() - 2];
		int t1 = t[t.size() - 1];

		int q1 = q[q.size() - 1];
		s.push_back(s2 - s1 * q1);
		t.push_back(t2 - t1 * q1);
	}

	// { x, y }
	pii ret = { s[s.size() - 1], t[t.size() - 1] };

	return ret;
}


// ax = 1 (mod M) 을 만족하는 x / gcd(x,M)=1 일때만 해가 있다.
long long modInv(int a, int M) {
	long long result = extendedGcd(a, M).first + M;
	result %= M;
	return result;
}


int main() {
	// 1. 입력받는다
	// freopen("input.txt", "r", stdin);
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		scanf("%d %d", &K, &C);

		// 1) 예외조건 - GCD(C, K) 는 반드시 1이다
		if (gcd(C, K) != 1) {
			printf("IMPOSSIBLE\n");
			continue;
		}

		// 2) 확장유클리드호제법
		ans = modInv(C, K);
		while (C*ans <= K) {
			ans += K;
		}

		// 3) 정답 출력
		if (ans > 1e9) {
			printf("IMPOSSIBLE\n");
		}
		else {
			printf("%lld\n", ans);
		}

	}

	return 0;
}
#endif