ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ] 캠프 준비
    Algorithm/BOJ 2020. 2. 8. 23:15

    [16938] 캠프 준비

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

    • 캠프에 사용할 문제를 고르는 방법의 수를 구하는 문제
    • N : 가지고 있는 문제 수
    • L : 문제 난이도 하한
    • R : 문제 난이도 상한
    • X : 가장 쉬운 문제와 가장 어려운 문제 난이도 차이
    • 1. 문제는 두 문제 이상
    • 2. 뽑은 문제의 난이도는 L 이상 R 이하
    • 3. 가장 쉬운 문제와 가장 어려운 문제의 난이도 차이는 X와 같거나 커야한다.

     

     

    Solution

    • permutation 활용 문제
    • 문제는 두 문제 이상이어야 하기 때문에 2 ~ N까지 size를 바꿔가면서 permutation() 함수를 돌렸다.
    • 뽑은 문제를 temp 리스트에 담아 문제의 조건에 부합하면 count++를 해주었다.

     

     

    소스코드

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.StringTokenizer;
    
    public class Main {
    	static int n, l, r, x, count;
    	static int[] a;
    	static List<Integer> p, temp;
    	static boolean[] c;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		StringTokenizer st = new StringTokenizer(sc.nextLine());
    		n = stoi(st.nextToken());
    		l = stoi(st.nextToken());
    		r = stoi(st.nextToken());
    		x = stoi(st.nextToken());
    		init();
    
    		st = new StringTokenizer(sc.nextLine());
    		for (int i = 0; i < n; i++) {
    			p.add(stoi(st.nextToken()));
    		}
    		count = 0;
    		for (int i = 2; i <= p.size(); i++) {
    			permutation(0, 1, i);
    		}
    		System.out.println(count);
    	}
    
    	public static void permutation(int depth, int start, int size) {
    		if (depth == size) {
    			temp = new ArrayList<>();
    			solve();
    			return;
    		}
    
    		for (int i = start; i <= n; i++) {
    			a[depth] = i;
    			permutation(depth + 1, i + 1, size);
    		}
    	}
    
    	public static void solve() {
    		for (int i : a) {
    			if (i == 0)
    				continue;
    			temp.add(p.get(i-1));
    		}
    		int min = Integer.MAX_VALUE;
    		int max = Integer.MIN_VALUE;
    		int sum = 0;
    		for(int i: temp) {
    			sum += i;
    			min = Math.min(min, i);
    			max = Math.max(max, i);
    		}
    		if(sum < l || sum > r)
    			return;
    		if(max - min < x)
    			return;
    		
    		count++;
    	}
    
    	public static void init() {
    		a = new int[n];
    		p = new ArrayList<>();
    	}
    
    	public static void print(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		System.out.println();
    	}
    
    	public static int stoi(String s) {
    		return Integer.parseInt(s);
    	}
    }
    

    'Algorithm > BOJ' 카테고리의 다른 글

    [BOJ] 배열 돌리기 1  (0) 2020.02.10
    [BOJ] 게리멘더링  (0) 2020.02.10
    [BOJ] 연구소 2  (0) 2020.02.08
    [BOJ] 치킨 배달  (0) 2020.02.08
    [BOJ] 배열 돌리기 4  (0) 2020.02.08

    댓글

Designed by Tistory.