1208

[백준 1208] 부분수열의 합2 C++

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 N이 40개 이므로 모든 부분수열을 다 구하려면 2^40번의 연산이 필요하다. -> 1초안에 풀 수 없다. 주어진 수열을 절반씩 나누어서 계산해 보자 수열의 길이가 40이라고 가정하자. 20번째 수열부터 40번째 수열(이를 right수열이라고 하자)까지의 모든 부분수열의 합을 구해본다. 이때 시간복잡도는 O(2^20)이므로 시간은 충분하다. right 부분 수열의 합을 sum이라고 하면 ..