BOJ_16938_캠프 준비
2021. 11. 12. 21:12ㆍ백준 알고리즘(BOJ)
1
구분: 수학, 부르트포스 알고리즘, 조합론, 백트레킹
언어: Java
- 전략:
문제를 선택한다 - 개수는 2개 이상 -> 부분 집합을 이용해 문제를 선택하거나 선택하지 않는다 - 문제들의 난이도들의 합을 구한다 -> 선택된 것들을 더한다
- 문제들의 최상 난이도 - 최하 난이도 차를 구한다 -> 배열의 정렬을 이용하여 최대, 최소값을 구한다
- 조건에 맞다면 개수를 1 증가
2. 코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n, l, r, x, ans;
static int[] level;
static boolean[] subset;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();//전체 문제 개수
l = scanner.nextInt();//합, 최소
r = scanner.nextInt();//합, 최대
x = scanner.nextInt();//차, 최소
level = new int[n];//문제 난이도
subset = new boolean[n];
ans = 0;
for(int i = 0; i<n; i++) {
level[i] = scanner.nextInt();
}
powerSet(0);
System.out.println(ans);
}//main
//부분 집합을 이용하여 문제를 선택
private static void powerSet(int cnt) {
if(cnt >= n) {
//선택된 문제의 수
int trueCnt = 0;
for(boolean b : subset) {
if(b) trueCnt++;
}
//2문제 이하면 안써
if(trueCnt<2)return;
int[] question = new int[trueCnt];
int idx = 0;
int sum = 0;//문제 난이도들의 합
//문제들의 난이도를 더하고, 정렬할 배열
for(int i = 0; i<n; i++) {
if(subset[i]) {
question[idx++] = level[i];
sum+=level[i];
}
}
//정렬하여 최소난이도, 최대 난이도를 구함
Arrays.sort(question);
//최상 난이도 - 최하 난이도
int sub = question[trueCnt-1] - question[0];
//조건에 맞으면 방법 수 증가
if(sum>=l && sum<=r && sub>=x) {
ans++;
}
return;
}
//부분 집합을 생성
subset[cnt] = true;
powerSet(cnt+1);
subset[cnt] = false;
powerSet(cnt+1);
}
}
3
- 문제의 수가 2개 이상인데 2개로 보고 조합을 구했었다.
- 난이도의 차가 x보다 크거나 같아야 하는데, 작거나 같다고 하였다
- 결론: 문제를 꼼꼼하게 읽자
'백준 알고리즘(BOJ)' 카테고리의 다른 글
BOJ_15721_번데기 (0) | 2021.12.07 |
---|---|
BOJ_11725_트리의 부모 찾기 (0) | 2021.11.19 |
BOJ_11279_최대 힙 (0) | 2021.11.11 |
BOJ_16987_계란으로 계란치기 (0) | 2021.11.08 |
BOJ_20056_마법사 상어와 파이어볼 (0) | 2021.10.23 |