BOJ(18429) - 근손실 (JAVA)

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

18429번: 근손실

 

• 백트래킹 탐색 문제이다. 
• 3대 500 이하 일시 바로 탐색을 종료해버리면 된다.

 

 

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

public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, K;
    private static int[] weights;
    private static boolean[] visit;
    private static int totalMethods;

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        weights = new int[N];
        visit = new boolean[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }

        dp(0, 500);
        System.out.println(totalMethods);
    }

    private static void dp(int depth, int weight) {
        if (depth > N) {
            return;
        }

        if (weight < 500) {
            return;
        }

        if (depth == N) {
            totalMethods += 1;
            return;
        }

        for (int i = 0; i < visit.length; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            dp(depth + 1, weight + weights[i] - K);
            visit[i] = false;
        }
    }
}