[백준]#1208 부분수열의 합 2
문제
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
풀이
이 문제는 모든 경우의 수를 구하면 최악의 경우 2^40 이기 때문에 수열을 반으로 나눠서 구하면 더 적은 시간복잡도로 답을 구할 수 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
public class Main {
static int N;
static int[] arr;
static HashMap<Integer, Integer> map;
static int S;
static long ans = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
S = Integer.parseInt(input[1]);
map = new HashMap<>();
arr = new int[N];
input = br.readLine().split(" ");
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(input[i]);
}
combination(0, N/2, 0);
combination(N/2, N, 0);
if(map.containsKey(S)) //앞 배열로 S를 만들 수 있는 경우
ans += map.get(S);
System.out.println(ans);
}
public static void combination(int index, int len, int sum) {
if(index==len)
return;
for(int i=index; i<len; i++) {
int nSum = sum+arr[i];
if(len==N/2) { //반으로 나눈 앞 배열의 모든 부분수열 합 구하기
if(map.containsKey(nSum)) { //hashmap에 합 종류와 갯수 저장
map.put(nSum, map.get(nSum)+1);
}
else {
map.put(nSum, 1);
}
}
else {
if(map.containsKey(S-nSum)) { //S에서 뒷 배열의 모든 부분수열의 합을 뺀 값이 hashmap에 존재하면 1증가
ans += map.get(S-nSum);
}
if(nSum==S) //뒷 배열 만으로 S를 구할 수 있는 경우
ans++;
}
combination(i+1, len, nSum);
}
}
}
Author And Source
이 문제에 관하여([백준]#1208 부분수열의 합 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준1208-부분수열의-합-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)