백준 1182. 부분수열의 합

🅰 백준 1182. 부분수열의 합

1182번: 부분수열의 합

✏️ 문제 풀이

• 부분수열의 합을 구하는 문제이다. 
• 일단 부분집합을 구하기 위해 subset 함수를 구현하였고, 부분집합이 완성될 때 마다 부분집합의 합을 계산하여 S의 값과 같으면 cnt++를 해주었다. 
• 부분집합을 구하면 공집합일때도 있기 때문에 공집합일 때에는 카운트 해주지 않기 위해 none을 카운트 해줘서 공집합일때를 예외처리 해주었다.

✏️ 소스코드

package bruteforce;

import java.util.*;
import java.io.*;
/*실버2 1182. 부분집합의 합*/
public class Main_S2_1182_손은성 {
	static boolean isSelected[];
	static int input[],count;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		isSelected = new boolean[N];
		input = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		
		subset(0,N,S);
		System.out.println(count);
	}

	// 부분집합 구하는 함수
	private static void subset(int cnt, int N, int S) {
		if(cnt == N) {
			int sum = 0;
			int none = 0;
			for (int i = 0; i < N; i++) {
				if(isSelected[i])
					sum+=input[i];
				else
					none++;
			}
			if(none!=N && sum == S)
				count++;
			return;
		}
		isSelected[cnt] = true;
		subset(cnt+1,N,S);
		isSelected[cnt] = false;
		subset(cnt+1,N,S);
	}

}

 

✅ 후기

•