[백준/JAVA] 16938번: 캠프 준비

📖 문제

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

 

 

💡  풀이 방식

• 백트래킹+ 브루트포스

1. 문제들을 배열에 입력받고, 이 배열을 난이도 기준 오름차순 정렬한다.

2. 2~N개까지 캠프에 사용할 문제들을 고른다. (백트래킹)

for(int i = 2 ; i <= N ; i++) {
    visited = new boolean[N];
    dfs(i, 0);
}

 

 

[백트래킹 함수]

  - (종료 조건) 목표 갯수만큼 뽑았다면, 문제에서 제시한 2가지 조건을 만족하는지 확인하고 방법 수를 갱신한다.

(여기서 리스트를 오름차순 정렬하지 않는 이유는, 이미 배열을 입력받고 오름차순 정렬해두어서 리스트에 저장할 때 이미 오름차순으로 난이도를 저장해 두기 때문이다.)

if(cnt == target) {
    int sum = 0;

    List<Integer> list = new ArrayList<>();
    for(int i = 0 ; i < N ; i++) {
        if(visited[i]) {
            list.add(i);
            sum += arr[i].lv;
        }
    }

    int diff = arr[list.get(list.size() -1)].lv - arr[list.get(0)].lv;	// 가장 어려운 문제와 가장 쉬운 문제 난이도 차
    if(sum >= L && sum <= R && (diff >= X)) {   // 1, 2번 조건 성립하는지 확인
        answer++;
    }

    return;
}

 

 

  -  i번 문제를 뽑는 반복문

for(int i = cnt ; i < N ; i++) {
    if(!visited[i]) {
        visited[i] = true;
        dfs(target, i + 1);
        visited[i] = false;
    }
}

 

 

 

 

💥 유의사항

종료 조건에서 리스트에 문제의 인덱스를 저장하는 것이므로, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이를 구할 때는 배열에서 해당 인덱스의 난이도 값을 가져와서 계산해야 한다.

int diff = arr[list.get(list.size() -1)].lv - arr[list.get(0)].lv;

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,L,R,X;
    static Node[] arr;
    static boolean[] visited;
    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 Node[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = new Node(i, Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(arr);   // 난이도 기준 오름차순 정렬
        
        // 캠프에 사용할 문제 2개 이상 고르기
        for(int i = 2 ; i <= N ; i++) {
            visited = new boolean[N];
            dfs(i, 0);
        }
        
        System.out.println(answer);
    }
    
    private static void dfs(int target, int cnt) { // 목표 갯수, 현재 뽑은 갯수
        // 목표 갯수만큼 뽑았으면 조건 만족하는지 확인하고 방법 수 갱신
        if(cnt == target) {
            int sum = 0;
            
            List<Integer> list = new ArrayList<>();
            for(int i = 0 ; i < N ; i++) {
                if(visited[i]) {
                    list.add(i);
                    sum += arr[i].lv;
                }
            }
            
            int diff = arr[list.get(list.size() -1)].lv - arr[list.get(0)].lv;
            if(sum >= L && sum <= R && (diff >= X)) {   // 1번 조건과 2번 조건 성립하는지 확인
                answer++;
            }
            
            return;
        }
        
        for(int i = cnt ; i < N ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(target, i + 1);
                visited[i] = false;
            }
        }
    }
}
 
class Node implements Comparable<Node> {
    int idx, lv;
    
    public Node(int idx, int lv) {
        this.idx = idx;
        this.lv = lv;
    }
    
    // 난이도 기준 오름차순 정렬
    @Override
    public int compareTo(Node n) {
        return this.lv - n.lv;
    }
}

 

 

 

➕ 다른 풀이 방식

- dfs 메소드의 파라미터에 최대 최소 난이도를 저장해 들고 다니며 조건을 만족하는지 확인하도록 푸셨다.

[백준] code.plus(브루트 포스 Part 1,JAVA)16938번, 캠프 준비

 

 

- 나처럼 리스트를 만들지 않고, 최대 난이도와 최소 난이도 값을 저장하는 변수만 만들어 활용하셨따. 그리고 dfs 함수 부분도 조금 다르심

백준 16938번 캠프 준비 (JAVA)

 

 

- 엄청 간단한 풀이 ㄴㅇㄱ

백준 16938번 : 캠프 준비(Java)

---

💦 어려웠던 점

- 푸는 데 17분, 디버깅 13분,,

- 내가 조금 복잡하게 푼 것 같다,,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V	240530

 

 

(+240530 2회독 : 23332KB, 200ms)

20분 소요...

20줄 정도 더 줄였다!

객체 안 만들고 그냥 배열 자체를 정렬했다. (문제 순서는 상관없길래,,,)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,L,R,X, answer;
    static int[] A;
    static boolean[] chk;
    
    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());
 
        A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);    // 미리 오름차순 정렬해두기
                
        for(int i = 2 ; i <= N ; i++) {    // 문제 2~N개 뽑기
            chk = new boolean[N];
            dfs(0, i);
        }
        System.out.println(answer);
    }
    
    private static void dfs(int cnt, int target) {
        if(cnt == target) {
            List<Integer> list = new ArrayList<>();    // 뽑은 숫자 저장 리스트
            int sum = 0;    // 뽑은 숫자들의 합
            
            for(int i = 0 ; i < N ; i++) {
                if(chk[i]) {    // 뽑은 숫자인 경우 > 리스트에 숫자를 저장하고, 합 갱신
                    list.add(A[i]);
                    sum += A[i];
                }
            }
            
            // L 이상 R 이하고, 리스트의 최대-최소 값이 X 이상인 경우 정답 갯수+1
            if(L <= sum && sum <= R && (list.get(list.size()-1) - list.get(0) >= X)) {
                answer++;
            }
            return;
        }
        
        for(int i = cnt ; i < N ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                dfs(i + 1, target);
                chk[i] = false;
            }
        }
    }
}