비둘기집 원리

비둘기집 원리(Dirichlet's Pigeonhole Principle)

조합론의 기본 원리이다.

 

간단하게 말한다면 

"비둘기가 N마리 있고 M개의 비둘기 집이 있다. 이때, N > M인 경우 하나의 비둘기 집에는 최소한 두 개 이상의 비둘기가 들어간다."

라는 내용이다

 

생각해보면 정말 당연한 소리다. 하지만 이 당연한 소리가 문제를 푸는데 큰 도움이 된다. 

 

 

백준 문제 중 20529번이 대표적으로 비둘기집 원리를 사용하는 문제다

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

20529번: 가장 가까운 세 사람의 심리적 거리

 

 

조만간 풀고 링크를 첨부하도록 하겠읍니다...