[JAVA]백준 1182번: 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

비트마스킹에 대한 글을 포스팅 한 후 금방 터득한 생생한 지식으로 바로 풀어보았다✨

 

 

 

| 문제 해결방법

 

부분집합 구하는 공식 + 비트마스킹

 

 

부분집합을 구할 때

1. boolean배열을 사용할 수도 있고

2. 비트마스킹 기법을 사용할 수도 있다.

 

이번 문제에서는 비트마스킹 기법을 사용하였고,

이 기법은 비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아니라 수행 속도가 빠르다는 장점이 있다.

 

 

[JAVA] 해설 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1182 {

	static int N, S, ans;
	static int[] arr;
	static int flag = 0;

	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());
		S = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		ans = 0;
		method(0, 0);
		System.out.println(ans);
	}

	// 부분집합 생성 메서드
	private static void method(int flag, int cnt) {

		if (cnt == N) {
			// 공집합인 경우
			if (flag == 0)
				return;

			int sum = 0;
			for (int i = 0; i < N; i++) {
				// i번째 비트가 1이라면 arr[i]값을 sum에 더하기
				if (((1 << i) & flag) > 0) {
					sum += arr[i];
				}
			}
			// 합이 S가 된다면 개수 추가
			if (sum == S)
				ans++;

			return;
		}

		// cnt번째 비트를 선택하지 않는 경우
		method(flag, cnt + 1);

		// cnt번째 비트를 선택한 경우
		flag = (1 << cnt) | flag;
		method(flag, cnt + 1);

	}

}

 

 

[제출] 메모리 및 시간