CEO

문제 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 앞서 다룬 부분수열의 합 문제에서 N의 범위가 40으로 증가한 문제이다. 따라서 기존의 풀이는 이 문제에 적용할 수 없다. 시간 초과가 발생하기 때문이다. 이 문제는 한 번에 N에 대한 부분수열을 모두 구하는 것이 아닌, 수열의 좌/우측으로 나누어 부분적으로 구한 후에 좌측의 작은 값 + 우측의 큰 값부터 점차적으로 계산해 S와 만족하는지 찾게 되면 시간 안에 문제를 해결할 수 있다. def dfs(idx,..