1208번: 부분수열의 합 2
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
예제 입력 1
5 0
-7 -3 -2 5 8
예제 출력 1
1
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int[] arr = null;
static ArrayList<Integer> first = null;
static ArrayList<Integer> second = null;
static int N, S, ans;
public static int lowerBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) >= target) {
max = mid;
}else {
min = mid + 1;
}
}
return max;
}
public static int upperBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) <= target) {
min = mid + 1;
}else {
max = mid;
}
}
return max;
}
public static void dfs(int dept, int end, int sum, ArrayList<Integer> list) {
if (dept == end) {
list.add(sum);
return;
}
dfs(dept + 1, end, sum + arr[dept], list);
dfs(dept + 1, end, sum, list);
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
arr = new int[N + 1];
first = new ArrayList<>();
second = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 배열을 절반으로 나눠 각각 부분집합의 합의 리스트를 구한다.
dfs(0, N / 2, 0, first);
dfs(N / 2, N, 0, second);
Collections.sort(first);
Collections.sort(second);
// 한 리스트에 대해 각 원소에 더했을 때 S를 완성할 수 있는 타겟의 수를 찾는다.
long ans = 0;
for(int i = 0; i < first.size(); i++) {
int target = S - first.get(i);
int upper = upperBound(second, target);
int lower = lowerBound(second, target);
ans += upper - lower;
}
System.out.println(S == 0 ? ans - 1 : ans);
}
}
codeung.tistory.com/223 이 문제에서 N 제한이 두 배로 늘어난 문제.
같은 방법으로 풀었다가 시간 초과를 맞았다.
N의 상한은 40이므로 같은 방법으로 풀면 O(2^N) = 약 1조의 값으로 터져버린다.
구글링을 통해 정답을 확인했고 현재 수준으로는 절대 혼자서 해결할 수 없는 문제였다.
"중간에서 만나기" (Meet in the middle) 방법을 사용해야 한다.
주어진 배열을 절반으로 나누어 각각 부분집합을 구한다.
(정확하게는 부분집합의 원소들을 모두 더한 값을 원소로 하는 리스트를 구한다.)
두 리스트에 대해서 서로의 원소의 합을 통해 S를 만들 수 있는 경우의 수를 구하면 된다.
이분탐색으로 target을 찾기 위해 먼저 정렬을 해놓아야 한다.
어차피 두 리스트 모두 처음 주어진 배열에 대한 부분집합이기 때문에 두 리스트의 원소를 더해서 S를 만들어도 상관 없다.
부분집합의 개수는 총 2^N개가 존재할 수 있고 이 경우 N의 상한이 40이므로 int 범위를 초과할 수 있기 때문에 long을 사용해야 한다.
이분 탐색을 사용한 upperBound(), lowerBound()는 그냥 외워버리자.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
| [BOJ] 2143 - 두 배열의 합 JAVA (0) | 2021.02.18 |
|---|---|
| [BOJ] 7453 - 합이 0인 네 정수 JAVA (0) | 2021.02.18 |
| [BOJ] 1261 - 알고스팟 JAVA (0) | 2021.02.16 |
| [BOJ] 1644 - 소수의 연속합 JAVA (0) | 2021.02.16 |
| [BOJ] 1806 - 부분합 JAVA (0) | 2021.02.16 |