[BOJ1208] 부분수열의 합 2

1. 문제

https://www.acmicpc.net/problem/1208

2. Note

2.1. Subset sum problem

Subset sum 문제라고 생각하여 O(nS)으로 해결하려 했습니다. 그러나 원소가 음수도 될 수 있다는 걸 간과하여 런타임 에러가 발생하였고, 이를 해결하기 위해 배열의 인덱스를 보정하여 접근하는 방식을 구현했지만 메모리 초과를 받았습니다.

2.2. 분할 정복의 아이디어

한 시간 넘게 해결하지 못하여 해법을 검색해봤는데 DP가 아닌 분할 정복으로 해결할 수 있다는 사실을 알게 되었습니다.