[C++] 비둘기집 원리와 응용

📗 비둘기집 원리

4개의 집이 있고 5마리의 비둘기가 있을 때
모든 비둘기에게 집을 할당하려면 '무조건' 중복된 집 할당이 생깁니다.
 
원리라고 부르기도 민망할 정도로 당연하고 직관적입니다.
 
살짝 확장을 해보자면
366명의 학생이 있을 때, 윤년을 고려하지 않으면 적어도 1명은 다른 한 명과 생일이 겹치겠죠?
이것이 '비둘기집 원리'입니다.
 
이 원리가 문제를 해결하는 데 있어, 존재를 증명할 때 종종 쓰이곤 합니다.
다음 예시를 통해 알아보도록 합시다.
 
 

📕 Decreasing Sequence 문제

---

1. 문제
주어진 두 정수 L과 R이 있을 때
다음 조건을 만족하는 가장 작은 양의 정수 N을 찾아라.
 
N% L > N%(L+1) >... > N%(R-1) > N% R
 
2. 입력
L = 4, R = 6을 입력했을 경우
 
3. 출력
출력은 6
 
4. 설명
6%4 = 2
6%5 = 1
6%6 = 0
 
이기 때문에, 조건을 만족하는 가장 작은 양의 정수 N은 
6이다.

---

 

📕 Brute Force로 풀기

가장 기본적인 아이디어는 
숫자 1부터 무한대 수 까지
조건을 만족할 때까지 모두 구해보는 것입니다.
 
코드는 다음과 같습니다.
 

#include <iostream>
#include <vector>
using namespace std;

int solve(int L, int R)
{
	int num = 1;
	bool right = false;
	vector<int> vec;
	
	while (true)
	{
		right = true;
		vec.clear();

		for (int i = L; i <= R; i++)
			vec.push_back(num % i);

		for (int i = 1; i < vec.size(); i++)
		{
			if (vec[i] >= vec[i - 1])
				right = false;
		}
	
		if(right)
		return num;
		else
			num++;
	}
}
int main()
{
	int L, R;
	cin >> L >> R;

	cout<< solve(L, R);

	return 0;
}

 
즉흥적으로 짠 코드라 가독성이 좋지 않으면 양해부탁드립니다.
 
이 코드는 1부터 무한대 수까지 무한 루프하면서
L~R 로 나머지 연산한 결과를 모두 배열에 삽입한 뒤
배열이 내림차순 인가?를 확인하는 코드 입니다.
 
이 경우, 주어진 문제를 해결할 수는 있지만
빅-오로 환산할 경우 O(n^2) 의 복잡도를 보입니다.
 
상당히 비효율적인 코드라고 할 수 있습니다.
 
 

📘 비둘기집 원리로 풀기

문제를 한 번 더 살펴봅시다.
 
임의의 정수 N을 구했을 경우
[L, R] 범위의 정수로 나머지를 취했을 때
나머지는 (R-L+1)개 존재합니다.
 
이 때, L이 가질 수 있는 나머지의 수는 L 개 이고
만약, R-L+1 > L 을 만족한다면, 절대 답이 나올 수 없습니다.
이 경우 '비둘기집 원리'에 의해서 무조건 중복된 나머지가 발생하게 되기 때문이죠.
 
그래서 답이 존재하기 위해서는
R-L+1 <= L 을 항상 만족해야 합니다.
 
R-L+1 <= L 을 만족한 경우, 가장 작은 N값은
항상 R이 됩니다.
 
N < L
일 경우 중복된 나머지가 발생하기에 조건을 만족할 수 없고
 
L <= N < R
일 경우 중복된 나머지가 발생하거나,
N % N = 0 (N < R)
N % R > 0 (R > N)
인 경우가 발생하기 때문에
조건을 만족할 수 없습니다.
 
그렇기에 N의 값은 항상
N >= R 이며
가장 작은 N은 R 인 것입니다.
 
그러므로 코드는 다음과 같습니다.
 

#include <iostream>
using namespace std;

int solve(int L, int R)
{
	int num = 1;

	if (R-L+1 > L)
		return -1;
	else return R;
}
int main()
{
	int L, R;
	cin >> L >> R;

	cout<< solve(L, R);

	return 0;
}

 
비둘기집 원리를 이용하여
해당 문제를 O(1) 이라는 매우 빠른 시간에 해결했습니다.
 
이 처럼 '존재성'을 확인하는 문제의 경우
비둘기집 원리를 이용하여 문제를 빠르게 해결할 수 있습니다.