[백준] 1450 냅색문제

---

DP에서 유명한 냅색 문제이지만, 이 문제는 최대 경우의 수가 2^30이기 때문에 DP를 통해서 해결할 수는 없다.

 

이전에 해결했던 부분수열의 합2와 같이 배열을 반으로 나누어 시간복잡도를 줄여야 한다. 주어진 하나의 배열을 Left, Right 2개의 배열로 나눈 후 부분수열을 구하는 알고리즘을 활용하여 원소들의 합을 구한다.

 

두 부분수열의 합 배열 중 하나만 선택하여 정렬하고, 나머지 하나의 배열의 원소를 주어진 C에서 빼 정렬한 배열을 Upper Bound 알고리즘을 통하여 문제를 해결한다.

 

Upper Bound 알고리즘은 주어진 값 보다 큰 원소가 나타나는 첫번째 위치를 반환하는 알고리즘이다. 반면 Lower Bound 알고리즘은 주어진 값 보다 크거나 같은 값이 나타나는 첫 번째 위치를 반환하는 알고리즘이다.

 

Python

Java