[백준 알고리즘] 1208번 부분수열의 합 2 node.js JavaScript JS
1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 😉문제 풀이 설명 문제에서 주어진 숫자는 최대 40개. 40개로 부분 수열을 만든다면 경우의 수가 2^40으로 시간초과가 됩니다. 따라서 다음과 같은 전략으로 문제를 풀 수 있습니다. 두 배열을 나누어서 경우의 수를 구합니다. 배열을 두 개로 나누면, 경우의 수가 2^20을 가진 배열 2개를 가지게 됩니다. 2^20은 100만번의 순회가 이루어져 시간 제한을 넘기지 않습니다. 따라서 두 배열 A와 B로 나눈 후 문제를 풉니..