[Baekjoon Online Judge] 1182 - 부분수열의 합 / Java

doooona 2021. 5. 28. 17:57

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

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

풀이1

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

public class Main {
	static int answer = 0, N, S, arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		subset(0, 0);
		System.out.println(S == 0 ? --answer : answer);
	}

	public static void subset(int cnt, int sum) {
		if (cnt == N) {
			if (sum == S) {
				answer++;
			}
			return;
		}

		subset(cnt + 1, sum + arr[cnt]);
		subset(cnt + 1, sum);
	}
}

풀이2 - boolean isSelected[] 배열 사용

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

public class Main {
	static int answer = 0, N, S, arr[];
	static boolean isSelected[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];
		isSelected = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		subset(0);
		System.out.println(S == 0 ? --answer : answer);
	}

	public static void subset(int cnt) {
		if (cnt == N) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) {
					sum += arr[i];
				}
			}
			if (sum == S) {
				answer++;
			}
			return;
		}

		isSelected[cnt] = true;
		subset(cnt + 1);
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}