분할 정복 썸네일형 리스트형 백준 16287 Parcel https://www.acmicpc.net/problem/16287 MITM? .. 모르겠다분할 정복으로 풀었다 4개를 고르는 경우를 모두 살펴야 하는데 $O(N^2)$까지 되는 제한이다.BOJ 9007 같은 느낌으로 일단 2개를 고르는 경우를 모두 구한 뒤 이를 잘 활용해 답을 구하고 싶어진다. $w$ 범위가 너무 크지 않으니 2개를 고르는 모든 경우에 대해 고른 두 수의 합을 인덱스로 사용하는 체크 배열을 만들면 합치는 과정은 $O(N^2)$ 정도에 할 수 있다. 2개를 고른 두 경우를 합칠 때 선택한 원소가 같으면 안 되니 배열을 반으로 나누어 한 쪽에서 2개, 다른 쪽에서 2개를 선택한다는 생각을 해볼 수 있다. 반으로 나누면 한 쪽에서 4개 모두 고르는 경우는 분할 정복처럼 처리할 수 있으니 .. 더보기 이전 1 다음
