백준 1208번 https://www.acmicpc.net/problem/1208
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
| 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, | S | ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. |
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
예제
입력
1
2
5 0
-7 -3 -2 5 8
출력
1
1
처음에는 모든 경우의 수를 확인하면 된다고 생각해서 다음과 같이 풀었는데 당연하게(?) 시간 초과가 나왔다. 아래 코드의 시간 복잡도는 O(2^n)이다. N이 40(최대값)일 때 2^40번의 연산을 해야하기 때문에 시간이 너무 오래 걸려서라고 생각한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Bj1208 {
public static int n, s, answer = 0;
public static int[] nums;
public static boolean[] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 1 ≤ N ≤ 40
s = Integer.parseInt(st.nextToken()); // |S| ≤ 1,000,000
st = new StringTokenizer(br.readLine());
nums = new int[n];
isVisited = new boolean[n];
for (int i = 0; i < n; i++)
nums[i] = Integer.parseInt(st.nextToken());
solution(0, 0);
if (s == 0) answer--;
System.out.println(answer);
}
public static void solution(int start, int sum) {
if (sum == s)
answer++;
for (int i = start; i < n; i++) {
if (!isVisited[i]) {
isVisited[i] = true;
solution(i+1, sum+nums[i]);
isVisited[i] = false;
}
}
}
}
내가 생각한것은 아니지만 이진탐색을 하면 된다고 한다.
이진탐색은 범위를 두 부분으로 나누어서 탐색하는 방법이다. 그렇기 때문에 한 번에 전부 탐색하는 것보다 속도가 빠르다.
- 입력받은 정수의 리스트를 두 부분으로 나눈뒤, 각 부분의 부분집합에 대한 합을 구한다.
여기서 공집합(즉, 0)도 포함이 되기 때문에 S=0일 경우에는 마지막에 처리해준다.
아래와 같이 0 ~ n/2와 n/2 ~ n로 나눠서 각 부분 집합에 대한 합 리스트를 구한다.
예를 들어, nums = {1, 2, 3}이라면 0 ~ 0, 1 ~ 2로 나눠져서 leftList = [0, 1], rightList = [0, 3, 2, 5]가 될 것이다.
1
2
getSumList(nums,0,n/2, 0, leftList);
getSumList(nums,n/2, n, 0, rightList);
1
2
3
4
5
6
7
8
9
// left부터 right까지 부분 집합에 대한 합 리스트를 구함
static void getSumList(int left, int right, int sum, ArrayList<Integer> list) {
if(left >= right) {
list.add(sum);
return;
}
getSumList(left+1, right, sum, list);
getSumList(left+1, right, sum+nums[left], list);
}
- leftList와 rightList를 정렬한다.
이진 탐색은 정렬되어 있어야지만 이용이 가능하기 때문에 정렬은 필수이다.
- leftList와 rightList에서 각각의 값을 합하여 s값과 일치하는지 비교한다.
수열은 집합과 다르게 중복이 가능하기 때문에 값이 중복되는 경우도 고려해야한다.
예를 들어, nums = {1, 2, 3, -3, 1, 2, 3}인 경우에는 rightList = [-3, -2, -1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6]가 될 것입니다. 0이 3개지만 다른 부분집합으로 인해 만들어진 것입니다.
그러므로 leftList에서의 중복되는 값과 rightList에서의 중복되는 값은 곱해주어야 합니다.
1
answer += leftCount * rightCount;
코드 (Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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 Bj1208 {
public static int n, s;
public static long answer = 0;
public static int[] nums;
public static boolean[] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 1 ≤ N ≤ 40
s = Integer.parseInt(st.nextToken()); // |S| ≤ 1,000,000
st = new StringTokenizer(br.readLine());
nums = new int[n];
isVisited = new boolean[n];
for (int i = 0; i < n; i++)
nums[i] = Integer.parseInt(st.nextToken());
// 1번 단계
ArrayList<Integer> leftList=new ArrayList<>();
ArrayList<Integer> rightList=new ArrayList<>();
getSumList(0,n/2, 0, leftList);
getSumList(n/2, n, 0, rightList);
// 2번 단계
Collections.sort(leftList);
Collections.sort(rightList);
// 3번 단계
int left=0, right=rightList.size()-1;
while(left < leftList.size() && right >=0) {
long leftValue = leftList.get(left);
long rightNum = rightList.get(right);
if(leftValue + rightNum == s) {
long leftCount = 0, rightCount = 0; // 중복된는 값 카운트하기
while(left < leftList.size() && leftList.get(left) == leftValue) {
leftCount++;
left++;
}
while(right >= 0 && rightList.get(right)== rightNum) {
rightCount++;
right--;
}
answer += leftCount * rightCount;
}
if(leftValue + rightNum > s) right--;
if(leftValue + rightNum < s) left++;
}
if(s==0) answer--;
System.out.println(answer);
}
static void getSumList(int left, int right, int sum, ArrayList<Integer> list) {
if(left >= right) {
list.add(sum);
return;
}
getSumList(left+1, right, sum, list);
getSumList(left+1, right, sum+nums[left], list);
}
}
메모리는 86364 KB, 시간은 960 ms가 걸렸다.