[BJ] 18429 : 근손실

       문제 요약        

- 문제

 

 

- 입출력

 

         아이디어        

 

백트래킹이란?

해를 찾는 도중에 더이상 해가 아님이 판별되면, 이전 단계로 되돌아가서 해를 찾아나가는 기법

 

조건 : K개 중 N개의 운동기구를 중복없이 (순서를 가지고) 선택

해가 아님이 판별되는 조건 : 운동기구를 선택했을 때 중량이 500미만

구해야하는 값 : 해의 개수 

         소스코드        

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B11123 {

    static int N, K;
    static int[] weight;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // N 일 동안, N개의 운동키트
        K = Integer.parseInt(st.nextToken()); // 하루 지날 때마다 K만큼 감소
        // 항상 500이상
        st = new StringTokenizer(br.readLine());
        weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }
        back(500, new boolean[N], 0);
        System.out.println(cnt);
    }

    static int cnt = 0;

    static void back(int curWeight, boolean[] visited, int day) {

        if (day == N) {
            cnt += 1;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
            if(curWeight + weight[i]-K>=500){
                visited[i] = true;
                back(curWeight + weight[i] - K, visited, day+1);
                visited[i] = false;
            }


        }
    }

}