[백준] 20529 - 가장 가까운 세사람의 심리적 거리 (비둘기집 원리)

예니·2021년 4월 20일
0

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

크리스마스엔가 백준 알고리즘 대회 문제였는데 당시에 한문제만 풀고 넘어간다고 틀린 상태로 그냥 뒀었다.
백준 프로필에 틀린 문제로 남아있는 것이 찝찝해서 재도전.

어떻게 풀어도 시간초과가 날 것 같아서 좀 찾아보니 비둘기 집 원리를 이용해야 풀 수 있다고 한다.


비둘기집 원리
(n+1)개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리

적용해보면

16가지 mbti가 있을때 k(k>16)명이 있으면 이 중 같은 mbti를 가지는 사람은 반드시 두 명 이상이다.

그러면
k>32이면 같은 mbti를 가지는 사람이 반드시 세 명 이상 있다는 것을 알 수 있다.

그렇다면 사람이 32명 넘게 있을 때는 무조건 답이 0이 된다.

엄청 간단한데 신기해서 메모

0개의 댓글