Meet in the middle (2) 썸네일형 리스트형 백준 4160 - 이혼 https://www.acmicpc.net/problem/4160 힌트 더보기 브루트 포스를 시행하면 $3^{24}$만큼 경우의 수가 있다. 밋 인 더 미들을 통해 $O(3^{12})$로 풀 수 있다. 풀이 더보기 다음 3가지를 한 번에 고려해보자. 잭이 가지는 집의 가치 질이 가지는 집의 가치 판매하는 집의 가치 3가지를 각각 따져서 브루트 포스로 잭의 집 가치와 질의 집 가치가 같은 경우를 찾으면 $3^{24}$만큼 경우의 수가 나오고 이는 매우 커서 30초라는 제한 시간 안에 어림도 없음을 알 수 있다. 밋 인 더 미들을 기법을 사용해 주어진 집을 2개의 부분 집합으로 쪼개자. 그러면 각 집합의 크기는 최대 12가 된다. 이때 우리는 다음을 구할 것이다. 분할된 집합을 각각 $s_{1}$, $s_{.. 백준 1208 - 부분수열의 합 2 www.acmicpc.net/problem/1208 주어진 조건에서 부분수열을 생성하는 경우는 $2^{40}$으로 단순한 완전 탐색으로 풀 수 없다. 주어진 수열을 절반으로 나눈 상황을 가정해보자. 각 부분에서 수열을 생성하는 경우는 완전탐색으로 $2^{20}$이고 두개의 부분을 탐색해야 하므로 $2 \times 2^{20}$가 되어 각 부분의 부분수열을 구한 후 서로 결합하는 방법으로 문제를 해결 할 수 있게 된다. 이처럼 상태 공간을 반으로 나누고 두 상태 공간의 접점을 탐색하는 기법을 meet in the middle이라 부른다. 주어진 수를 서로 다른 배열에 담아 비트마스킹으로 부분수열의 합을 벡터에 저장하고 각 벡터에서 s의 개수 + 각 벡터에 있는 원소를 더했을 때 s가 되는 경우의 수를 구하.. 이전 1 다음
