[Algorithm/Java] SWEA 1486번 - 장훈이의 높은 선반

---

1486. 장훈이의 높은 선반

---

🔍 문제 풀이

문제 도식화

💻 코드

전체 코드

import java.io.*;
import java.util.*;

public class Solution {
    static int n, b, ans;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 점원 수
            b = Integer.parseInt(st.nextToken()); // 선반의 높이

            arr = new int[n];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            ans = Integer.MAX_VALUE;
            dfs(0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs(int depth, int sum) {
        // 1. 가지치기
        if(ans <= sum-b) return;

        // 2. 종료조건
        if(depth == n){
            if(sum >= b) ans = Math.min(ans, sum - b);
            return;
        }

        // 3. 백트래킹
        // (1) 선택o
        dfs(depth + 1, sum + arr[depth]);

        // (2) 선택x
        dfs(depth + 1, sum);
    }
}

스켈레톤 코드

import java.io.*;
import java.util.*;

public class Solution {
    static int n, b, ans;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 점원 수
            b = Integer.parseInt(st.nextToken()); // 선반의 높이

            arr = new int[n];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            ans = Integer.MAX_VALUE;
            dfs(0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs() {

    }
}