https://www.acmicpc.net/problem/20529
크리스마스엔가 백준 알고리즘 대회 문제였는데 당시에 한문제만 풀고 넘어간다고 틀린 상태로 그냥 뒀었다.
백준 프로필에 틀린 문제로 남아있는 것이 찝찝해서 재도전.
어떻게 풀어도 시간초과가 날 것 같아서 좀 찾아보니 비둘기 집 원리를 이용해야 풀 수 있다고 한다.
비둘기집 원리
(n+1)개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리
적용해보면
16가지 mbti가 있을때 k(k>16)명이 있으면 이 중 같은 mbti를 가지는 사람은 반드시 두 명 이상이다.
그러면
k>32이면 같은 mbti를 가지는 사람이 반드시 세 명 이상 있다는 것을 알 수 있다.
그렇다면 사람이 32명 넘게 있을 때는 무조건 답이 0이 된다.
엄청 간단한데 신기해서 메모
