ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [BOJ] 근손실
      Algorithm/BOJ 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
       
       
      		  
       
       
      		  

      'Algorithm > BOJ' 카테고리의 다른 글

      [BOJ] 빵집(JAVA)  (0) 2021.01.25
      [BOJ] 월드컵(JAVA)  (0) 2021.01.24
      [BOJ] 계란으로 계란치기  (0) 2021.01.20
      [BOJ] 청소년 상어  (0) 2021.01.19
      [BOJ] 아기상어  (0) 2021.01.12

      관련글 관련글 더보기

      댓글

    Designed by Tistory.

    티스토리툴바