문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오해설발상이 어려웠던 문제다. 수열의 최대 크기가 40인데, 백트래킹(브루트포스)로 전체 경우를 구하게 되면 O(n^40)으로 시간초과가 발생한다. 이때, 수열을 절반으로 나누어 각 수열마다 O(n^20) + O(n^20) 의 시간복잡도를 가지게 하면 시간 내에 풀 수 있게 된다. 먼저, 다음과 같이 길이가 10인 수열이 있고, 합이 0이 되는 경우를 구한다고 가정해보자.# Input10 01 2 3 4 5 -1 -2 -3 -4 -5 먼저 수열을 절반으로 나눌 것이다.그러면 다음과 같이 left, right 두 개의 리스트를 얻을 수 있다. # lef..
