부분집합 [BOJ 26938] 캠프준비

📌 풀이

순열 / 중복순열 / 조합 / 부분집합의 문제의 경우에는 어느정도 스스로 정형화가 되어가고 있는 듯 하다.

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

위의 문제는 각기 다르거나 같은 난이도를 가진 문제들을
각각 사용할지 말지를 결정한 다음
결정한 경우에 수에 대하여 조건에 맞는 경우만을 카운팅 하는 간단한 문제였다.

각각의 문제에 대해 사용 / 비사용을 결정하므로
부분집합 문제라고 볼 수 있다.

private static void subset(int lev, int[] res) {
		if (lev == N) {
			int ones = 0;
			for (int i = 0; i < res.length; i++) {
				if (res[i] == 1)
					ones++;
			}
			if (ones > 1)
				if (checkPossible(res))
					ans++;
		} else {
			res[lev] = 1;
			subset(lev + 1, res);
			res[lev] = 0;
			subset(lev + 1, res);
		}
	}

부분집합 문제는 비트마스킹으로도 경우의 수를 탐색할 수 있지만 DFS로 재귀적으로 탐색하는 방식으로 구현했다.

0(사용안한다는 의미)인 경우를 체크하고 재귀호출, 1(사용한다는 의미)일 경우를 체크하고 재귀호출을 돌아

0 0 0
0 0 1
0 1 0
1 0 0
1 1 0
1 0 1
0 1 1
1 1 1

의 res 배열을 가져온다.
문제의 조건에 따라 모두 안고르거나 하나만 고르는 경우는 고려하지 않으므로

int ones = 0;
			for (int i = 0; i < res.length; i++) {
				if (res[i] == 1)
					ones++;
			}
            if (ones > 1)
				if (checkPossible(res))
					ans++;

계산하지 않을 res 배열을 제외하고 checkPossible함수를 돌렸다.

private static boolean checkPossible(int[] res) {
		int sum = 0;
		int min = 0;
		int max = 0;
		boolean isMinChecked = false;

		for (int i = 0; i < N; i++) {
			if (res[i] == 1) {
				sum += problems[i];
				if (!isMinChecked) {
					min = problems[i];
					isMinChecked = true;
				}
				max = problems[i];
			}

		}
		if (sum < L || sum > R)
			return false;

		if (max - min < X)
			return false;

		return true;
	}

백트래킹으로 DFS를 돌면서 sum을 계산하고 값이 조건보다 큰 경우에 탐색을 중지하는 식의 백트래킹을 했으면 더 효율적이지 않았을까 싶다.

📌 전체 코드

package week8;

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

public class BOJ16938_캠프준비 {

	static int N;
	static int L;
	static int R;
	static int X;
	static int[] problems;
	static int ans;

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		problems = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			problems[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(problems);
		subset(0, new int[N]);
		System.out.println(ans);

	}

	private static void subset(int lev, int[] res) {
		if (lev == N) {
			int ones = 0;
			for (int i = 0; i < res.length; i++) {
				if (res[i] == 1)
					ones++;
			}
			if (ones > 1)
				if (checkPossible(res))
					ans++;
		} else {
			res[lev] = 1;
			subset(lev + 1, res);
			res[lev] = 0;
			subset(lev + 1, res);
		}
	}

	private static boolean checkPossible(int[] res) {
		int sum = 0;
		int min = 0;
		int max = 0;
		boolean isMinChecked = false;

		for (int i = 0; i < N; i++) {
			if (res[i] == 1) {
				sum += problems[i];
				if (!isMinChecked) {
					min = problems[i];
					isMinChecked = true;
				}
				max = problems[i];
			}

		}
		if (sum < L || sum > R)
			return false;

		if (max - min < X)
			return false;

		return true;
	}

}