SWEA 2817_부분 수열의 합

비트연산을 쓴다. 

import java.util.Scanner;

public class Solution {
	
	public static int loop;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		loop = sc.nextInt();
		for(int i = 0; i<loop; i++) {
			int size = sc.nextInt();
			int wanted = sc.nextInt();
			
			int[] arr = new int[size];
			for(int j = 0; j<size; j++) {
				arr[j] = sc.nextInt();
			} // 배열 채우기
			
			int count = 0;
			for(int j = 0; j<(1<<size); j++) {
				int sum = 0;
				for(int k = 0; k<size; k++) {
					if((j & (1<<k)) > 0) {
						sum += arr[k];
					} 
				}
				if(sum == wanted) count++;
			}
			
			System.out.printf("#%d %d\n", i+1, count);
		}
	}
}

 

여기서 알아두면 좋은 점

 for(int j = 0; j<(1<<size); j++) {

   for(int k = 0; k<size; k++) {

     // 회차마다 조합이 하나씩 생긴다

     if((j & (1<<k)) > 0) {

              // 이 구역 안에 들어오는 요소가 해당 조합을 이루는 원소

     } // if

   } // for int k

 } // for int j

size개의 요소 중 나올 수 있는 조합을 모두 구할 때(개수 상관 없이, all 부분집합)

<<와 & 연산자를 통해 위 구조를 이용하면 쉽게 구할 수 있다.