완전 탐색 (1) 썸네일형 리스트형 백준 4160 - 이혼 https://www.acmicpc.net/problem/4160 힌트 더보기 브루트 포스를 시행하면 $3^{24}$만큼 경우의 수가 있다. 밋 인 더 미들을 통해 $O(3^{12})$로 풀 수 있다. 풀이 더보기 다음 3가지를 한 번에 고려해보자. 잭이 가지는 집의 가치 질이 가지는 집의 가치 판매하는 집의 가치 3가지를 각각 따져서 브루트 포스로 잭의 집 가치와 질의 집 가치가 같은 경우를 찾으면 $3^{24}$만큼 경우의 수가 나오고 이는 매우 커서 30초라는 제한 시간 안에 어림도 없음을 알 수 있다. 밋 인 더 미들을 기법을 사용해 주어진 집을 2개의 부분 집합으로 쪼개자. 그러면 각 집합의 크기는 최대 12가 된다. 이때 우리는 다음을 구할 것이다. 분할된 집합을 각각 $s_{1}$, $s_{.. 이전 1 다음
