Algorithm/BOJ

[BOJ] 근손실

goakgoak 2021. 1. 20. 22:50

[18429] 근손실

www.acmicpc.net/problem/status/18429/3/1

 

Solution

  • 가장 기본적인 백트래킹 유형이라고 할 수 있다.
  • N은 물론 8이하이고, 모든 순열에 대해 문제의 조건을 충족하는 경우(근손실 없이 N개의 운동 장비를 사용할 수 있는지)만 카운트한다.

 

 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n, k, answer;
    static int[] order;
    static Kit[] info;
 
    static class Kit {
        private int weight;
        private boolean used;
 
        public Kit(int weight, boolean used) {
            this.weight = weight;
            this.used = used;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        k = stoi(st.nextToken());
 
        order = new int[n];
        info = new Kit[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            info[i] = new Kit(stoi(st.nextToken()), false);
        }

// 시작 번호는 고정 (0 ~ N-1)
        answer = 0;
        for (int i = 0; i < n; i++) {
            int sum = 500 + info[i].weight - k;
            if(sum >= 500){
                info[i].used = true;
                dfs(i, 1, sum);
                info[i].used = false;
            }
        }
 
        System.out.println(answer);
 
    }
 
    private static void dfs(int num, int count, int sum) {
       // N개의 운동 장비를 모두 사용했을 때 카운트
if (count == n) {
            answer++;
            return;
        }
 
        for (int i = 0; i < n; i++) {
            if (!info[i].used && (sum + info[i].weight - k) >= 500) {
                info[i].used = true;
                dfs(i, count + 1, sum + info[i].weight - k);
                info[i].used = false;
            }
        }
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}
 
 
 cs