-
[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