재밌는 문제였다. 이 문제를 전날 자기 전부터 고민해서 일어나서 랩실을 가서 풀었는데, 핵심적인 관찰이 재밌고, 그 결과까지의 과정이 재밌는 문제였다. 추천! Support Group에 사람이 포함되면 그 사람에 대응되는 정점을 선택한다고 하자. 관찰 1. 크기가 n인 clique가 있을 때, 그 clique에 포함되는 정점중 n-1개는 무조건 포함해야 한다. 관찰 1번은 나름 쉽게 떠올릴 수 있다. 우선 문제 지문에서부터 clique를 이용해야 하기에, 당연히 떠올릴 수 있고, 만약 n-2개 이하로 포함 한다면 포함되지 않는 새로운 clique가 생겨서 모순이다. 여기까지 생각한 후 생각의 전개는 다음과 같다. 1개만 교체할 수 있다면, 1개를 빼고 새로운 x개로 넣을 텐데, x가 1이라면 편하다.....
