각박한 세상에서 정신체리

3955번: 캔디 분배 (acmicpc.net)

1. 전체 코드

#include <iostream>
#include <cmath>

using namespace std;

long long gcd(long long k, long long c);
long long distribute_candy(long long k, long long c);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	long long k, c;
	for (int i = 0;i < t;i++) {
		cin >> k >> c;
		if (k == 1) {	
			if (c == 1) cout << "2\n";
			else cout << 1 << '\n';
			// cout << "2\n";로 경우 합쳐도 상관없음
		}
		else {
			if (c == 1 && k != pow(10, 9)) {
				cout << k + 1 << '\n';
			}
			else {
				long long res = distribute_candy(k, c);
				if (res == -1) {
					cout << "IMPOSSIBLE\n";
				}
				else {
					cout << res << '\n';
				}
			}
		}
	}
}


long long gcd(long long k, long long c) {
	if (c == 0) return k;
	return gcd(c, k % c);
}

long long distribute_candy(long long k, long long c) {
	if (gcd(k, c) != 1) return -1;

	// 초기화
	long long s0 = -1, s1 = 0, t0 = 0, t1 = 1;
	long long r0 = k, r1 = c;
	long long tmp = 0, q = 0;

	while (r1) {
		q = r0 / r1;
		tmp = r0;
		r0 = r1;
		r1 = tmp - r0 * q;

		tmp = s0;
		s0 = s1;
		s1 = tmp - s0 * q;

		tmp = t0;
		t0 = t1; 
		t1 = tmp - t0 * q;

	}

	if (s0 < 0 && t0 < 0) {
		s0 += c;
		t0 += k;
	}

	if (s0 <= 0 || t0 <=0 || t0 > pow(10, 9)) {
		return -1;
	}
	else {
		return t0;
	}

}

2. *•.¸♡ 코⊑ 뜯ન보⌝ᥣ ♡¸.•*

2.1 헤더파일

#include <cmath>

pow를 쓸 때 필요. 처음에 이거 안 넣어서 컴파일 에러 떴다...

2.2 함수

2.2.1 최대공약수를구하는 함수 : "유클리드 호제법 "

long long gcd(long long k, long long c) {
	if (c == 0) return k;
	return gcd(c, k % c);
}

2.2.2 -Kx+Cy = 1의 해를 구하는 함수 : "확장 유클리드 호제법"

if (gcd(k, c) != 1) return -1;

: k와 c가 서로소가 아니라면 -1, 즉 IMPOSSIBLE을 출력한다.

왜 서로소여야할까?

확장 유클리드 호제법의 정의를 되새겨보자.... 

확장 유클리드 호제법이란 Ax+By = gcd(A, B)를 만족하는 x, y를 구하는 알고리즘이다.

우리는 문제의 조건에서 우변이 이미 1로 고정되어 있다. 즉, gcd(A, B) = 1이어야 하는 것은 문제의 전제 조건이다. 

잘 이해가 가지 않는다면 반례를 생각해보면 된다. 주어진 예제 입력에서 K=10, C=5인 경우를 생각해보자. 

-10x + 5y을 통해 우리는 -5, 0, 5, 10, .... 5의 배수를 만들 수 있다.(확장 유클리드 호제법의 정의와도 같다. 10과 5의 최대공약수인 5의 배수만을 만들 수 있다!)

즉, K와 C가 서로소가 아니라면 절대 1을 만들 수 없다. 

따라서 불필요하게 뒤의 코드를 진행할 필요 없이 바로 -1, 즉 IMPOSSIBLE을 리턴해준다. 

2.3 - Kx+Cy => K 앞의 -1 처리 : 계수가 음수인 경우?

나머지 함수는 확장 유클리드 호제법의 정의에 따라 작성하면 된다!

다만, 이 문제에서는 특이점이 있다. 바로 ax+by에서 a>0, b>0인 일반적인 경우와 달리, 계수가 음수인 문제 조건이다. 

이 부분은 기존 코드에서 초기화 상태만 바꿔주면 된다. 원리를 생각해보면 된다. 

17x + 5y의 경우를 생각해보자

원래대로라면,

1*x + 0*y = 17   // 1번 식
0*x + 1*y = 5     // 2번 식

로 우리는 식을 나눌 것이다.

하지만!! 여기서 우리는 -17로 부호를 바꿔주고 싶으므로 1번 식의 좌변에 -1을 곱해주면 된다.

(-1)*x + 0*y = 17   // 1번 식
0*x + 1*y = 5        // 2번 식

거꾸로 1번식과 2번 식을 합쳐보면, -17x + 5y가 된다. 

따라서 초기화하는 코드를 작성해보면 이렇다

s0 = -1에 주목하자.

// 초기화
	long long s0 = -1, s1 = 0, t0 = 0, t1 = 1;
	long long r0 = k, r1 = c;
	long long tmp = 0, q = 0;

2.4 반복문 돌리기

while (r1) {
		q = r0 / r1;
		tmp = r0;
		r0 = r1;
		r1 = tmp - r0 * q;

		tmp = s0;
		s0 = s1;
		s1 = tmp - s0 * q;

		tmp = t0;
		t0 = t1; 
		t1 = tmp - t0 * q;

	}

s0를 s1으로, t0를 t1으로, r0를 r1으로..... tmp를 거쳐서 계속 값을 업데이트 해주는 부분이 직관적으로 이해하기 어려울 수 있다! 이럴 때는 그냥 특정한 값을 예시로 잡고 코드를 직접 따라가보면 된다. 

2.5 x, y가 음수가 나올 땐??

예제 입력 중,

1337 23

이게 진짜 처음에 처리가 안됐다.....

while문까지 돌린 다음, s0, t0의 값을출력해보면, 각각 -8, -465가 나온다. 

문제 조건 상, 우리는 사탕을 음수 개수만큼 나눠주고, 음수 개수만큼 구매하는 것은 불가능하므로 음수를 죄다 양수로 바꿔줘야 한다. 

if (s0 < 0 && t0 < 0) {
		s0 += c;
		t0 += k;
	}

-8은 -8+23 = 15로, 

-465는 -465+1337 = 872로 변환해준다는 의미이다. 

사실.... 경험적 사실로 알아냈다. +이 부분은 더 추가할 수도...

2.6 예외 처리

마지막으로 불가능한 경우를 한 번 더 걸러줘야한다. 

1. x는 자연수일 것 -> 사탕 최소 1개씩은 나눠준다는 의미. 문제에 명시함
2. y도 자연수일 것 -> y가 0이하는 사탕을 하나도 안 사겠다는 것. 1번 조건에 위배됨.
3. 선영이는 부자가 아니기 때문에 10^9개를 넘는 사탕 봉지(==y)는 구매하지 못한다. 

즉, 다시 말해서

1. x가 자연수가 아니라면 불가능
2. y가 자연수가 아니라면 불가능
3. y가 10^9보다 크면 불가능 

그대로 코드로 작성하면 된다. 불가능한 조건 하나라도 걸리면 사탕 분배가 불가능한 경우이므로 or로 연결해준다. 

if (s0 <= 0 || t0 <=0 || t0 > pow(10, 9)) {
		return -1;
	}
	else {
		return t0;
	}

불가능한 조건에 걸리지 않는 다면 y값, 즉 t0를 반환하고 끝이 난다.

2.7 입력 예외 처리

이번에는 입력 예외 처리이다!!

방금 전 우리가 한 것은 유클리드 호제법을 통해 구한 x, y값에 대한 예외 처리였다.

입력 예외 처리는 k, c값에 따른 예외 처리이다. 

2.7.1 K = 1 : 친구가 한 명만 왔을 때...

선영이는 최소 x+1개의 사탕을 준비해야 한다. 

이때 x는 자연수이므로 최대 2개의 사탕이 필요하다. 

여기서 또 경우가 두 개로 나뉜다.

C = 1

사탕은 2개가 필요한데, 사탕봉지 당 1개의 사탕만 들어있다. 우린 최소 2봉지의 사탕이 필요하다  

C >= 2

사탕은 2개가 필요한데, 이미 1개의 사탕 봉지당 2개 이상씩 들어있다. 이때 1봉지만 사도 충분하다

사실 문제에서 가능한 봉지의 수가 여러개라면 아무거나 출력하라고 했기 때문에, y의 값은 1이상이기만 하면 된다.

결국 c=1일때 경우와 합쳐서 2봉지가 필요하다가 출력해도 상관없다. 

if (k == 1) {	
			if (c == 1) cout << "2\n";
			else cout << 1 << '\n';
			// cout << "2\n";로 경우 합쳐도 상관없음
		}

2.7.2 C = 1 : 옹졸한 사탕 판매..

우리가 필요한 사탕의 개수는 K*x+1개이다.

사탕봉지 1개당 1개의 사탕만 들어있으므로 K*x+1개의 사탕봉지가 필요하다.

그러나!! 하지만 선영이는 부자가 아니기 때문에 10^9개를 넘는 사탕 봉지를 구매하지 못한다.

만약, K = 10^9라면 사탕은 최소 10^9+1개가 필요하고 10^9개의 넘는 사탕 봉지가 필요하다.

즉 K != 10^9라는 조건을 추가로 걸어준다.

if (c == 1 && k != pow(10, 9)) {
				cout << k + 1 << '\n';
			}

3. 반례 모음

개인적으로 질문 게시판의 반례 모음글이 많은 도움이 되었다.

글 읽기 - 반례 모음 (acmicpc.net)