Pigeonhole Principle (1) 썸네일형 리스트형 50. Pigeonhole Principle 비둘기집의 원리(Pigeonhole Principle)는 $(n+1)$개의 물건을 $n$개의 상자에 빠짐없이 넣은 경우 최소한 한 개의 상자에는 두 개 이상의 물건이 들어간다는 원리로, 보통 비둘기와 비둘기집에 빗대어 표현하기 때문에 이런 이름을 가지게 되었다. 이를 일반화하면 $n$개의 물건을 $m$개의 상자에 빠짐없이 넣었을 때 $\lceil n/m \rceil$개 이상의 물건이 들어간 상자가 하나 이상 존재한다는 의미가 된다. 이 원리를 이용해서 풀 수 있는 문제들의 경우 제대로 접근하지 못하면 괜히 어려운 풀이를 생각하다가 헤매기 쉬우므로 주의해야 한다. [연습문제] BOJ 21099. Four XOR (Platinum V) 더보기 $n$개의 수의 범위가 $10$만 이하이므로 여기서 임의로 $2$.. 이전 1 다음
