[백준] 1182 부분수열의 합

문제

---

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 

 

풀이

---

하나씩 수열을 직접 선택하면서 하는 경우도 있겠지만, 이렇게 하는경우에는 시간이 오래걸린다.

 

비트마스킹을 이용해서 수열을 만들 수 있다.

 

만약 n 이 5라면

00001 ~ 11111 까지로 표현된 2진수를 이용해서 생각해보면

 

5번째	4번째	3번째	2번째	1번째
0	0	0	0	1

위와 같은 방식으로 생각하면된다. 00001 이라면 1번째 숫자만 선택하는 것이다.

00011 이면 1번째 2번째 숫자를 선택하여 이 둘의 합을 구하면 된다.

 

이렇게 하면 5가지의 숫자를 조합 할  수 있는 모든 경우의 수를 쉽게 판단할 수 있다.

 

이것일 코드로 표현하면 아래와 같다.

for(int i = 1 ; i < (1 << n) ; i++) {
	
	int sum = 0;
	for(int j = 0 ; j < n ; j++) {
		if((i & (1 << j)) != 0) {
			sum += arr[j];
		}
	}
	
	if(sum == s) {
		answer++;
	}
}

i 와 1 << j 의 &(AND) 연산을 한 값이 0이 아니라면 해당 숫자가 포함이 된다는 것이므로 값을 더해주면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int[] arr;
		
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		int n = parseInt(st.nextToken());
		int s = parseInt(st.nextToken());
		
		st = new StringTokenizer(bufferedReader.readLine());
		arr = new int[n];
		for(int i = 0 ; i < n ; i++) {
			arr[i] = parseInt(st.nextToken());
		}
		
		int answer = 0;
		for(int i = 1 ; i < (1 << n) ; i++) {
			
			int sum = 0;
			for(int j = 0 ; j < n ; j++) {
				if((i & (1 << j)) != 0) {
					sum += arr[j];
				}
			}
			
			if(sum == s) {
				answer++;
			}
		}
		
		System.out.println(answer);
	}	
}