[백준] 16938 캠프 준비 - DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) JAVA

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

16938번: 캠프 준비

코드설명

DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) 를 활용하는 문제입니다.

 

처음에는 KnapSack(냅색, 배낭문제)을 활용해서 완전탐색을 하는 경우로 생각해야해나했지만, 재귀를 활용한 완전탐색 및 브루트포스를 진행했습니다.

 

코드로직입니다.

1. simulate 함수는 재귀적으로 부분 집합을 생성하면서 조건에 맞는 경우를 찾습니다.
   • level: 현재까지 선택한 원소의 개수를 나타냅니다.
   • sum: 현재까지 선택한 원소들의 합을 나타냅니다.
   • idx: 선택할 현재 원소의 인덱스를 나타냅니다.
   • min: 현재까지 선택한 원소들 중에서 가장 작은 값을 나타냅니다.
   • max: 현재까지 선택한 원소들 중에서 가장 큰 값을 나타냅니다.
2. 기저 조건을 확인합니다:
   • 만약 level이 N을 초과하면 함수를 종료합니다.
3. 합이 주어진 범위 [L, R] 내에 있고, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이가 X 이상인 경우, answer를 증가시킵니다.
4. 현재 인덱스부터 배열 끝까지 반복하면서 다음 원소를 선택하고, simulate 함수를 재귀적으로 호출합니다.

처음에 실수했던 점은,  아래의 코드에서 return 을 진행했다는 점입니다.

sum은 >= L, sum<=R이기에 범위내에 존재하면 가능한것인데 한번 발견하고 바로 기저조건으로 판단하고 종료시키기에 완전탐색이 불가합니다. 즉, 하나의 조합에서 경우를 발견하면 바로 종료한다는점 입니다.

return 은 level이 초과하는, 즉 현재까지 선택한 원소의 개수가 N개를 넘어가면 종료시킴으로써 완전탐색합니다.

if(level >= 2 && sum >= L && sum <= R) { //만약 합이 더 커진다면 안됩니다.

    if( max - min >= X) { //가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야한다.
        answer += 1;
    }
//    		return ; 여기서 중단시키면 완전탐색이 안됩니다. 모든 조합을 구하기 위해 return은 level값이 넘어갈경우 중단시킵니다.
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, L, R, X;
    public static int[] arr;
    public static int answer = 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());
        L = Integer.parseInt(st.nextToken()); 
        R = Integer.parseInt(st.nextToken());
        X = 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());
        }
        simulate(0, 0, 0, Integer.MAX_VALUE, 0);
        System.out.println(answer);
    }
    
    public static void simulate(int level, int sum, int idx, int min, int max) {
    	if(level > N) return ; //만약 N개보다 더 많이 더해지는경우는 없습니다.
    	if(level >= 2 && sum >= L && sum <= R) { //만약 합이 더 커진다면 안됩니다.
    		
    		if( max - min >= X) { //가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야한다.
    			answer += 1;
    		}
//    		return ; 여기서 중단시키면 완전탐색이 안됩니다. 모든 조합을 구하기 위해 return은 level값이 넘어갈경우 중단시킵니다.
    	}
    	
    	for(int i=idx; i<N;i++) {
			simulate(level + 1, sum + arr[i], i + 1, Math.min(min, arr[i]), Math.max(max, arr[i]));	
    	}
    }

}