[백준 - 16938] 골드4 캠프 준비 (조합)

www.acmicpc.net/problem/16938

16938번: 캠프 준비

1. 유형

조합

 

2. 풀이

조합 베이스 코드에다가 기저조건을 요구사항대로 만들면 된다.

 

3. 코드

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

public class back_16938캠프준비 {
	static int N,L,R,X,inp[], sel[], answer=0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.valueOf(st.nextToken());
		L = Integer.valueOf(st.nextToken());
		R = Integer.valueOf(st.nextToken());
		X = Integer.valueOf(st.nextToken());
		inp = new int[N];
		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			inp[i] = Integer.valueOf(st.nextToken());
		}
		sel = new int[N];
		comb(0, 0, 0);
		System.out.println(answer);
	}
	static void comb(int idx, int sidx, int sum) {
		if(idx==N) {
			if(sum>=L && sum<=R) {
				int max=0,min=Integer.MAX_VALUE;
				for (int i = 0; i < sidx; i++) {
					max = Math.max(max, sel[i]);
					min = Math.min(min, sel[i]);
				}
				if((max - min) >= X) {
					answer++;
				}
			}
			return;
		}
		sel[sidx] = inp[idx];
		comb(idx+1, sidx+1, sum+inp[idx]);
		comb(idx+1, sidx, sum);
	}
}

 파라미터로는 배열의 인덱스, 선택 배열 인덱스, 선택한 요소의 합

static void comb(int idx, int sidx, int sum)

N개를 선택했을 때 선택을 멈추고 조건을 탐색

if(idx==N) {
	if(sum>=L && sum<=R) {