[Baekjoon 18429 / Java / 실버3] 근손실

문제

 

기본 3대중량은 500이다.

매일매일 중량은 K 씩 감소한다.

매일매일 하나의 운동 키트를 사용하여 중량을 증가시킬 수 있다.

 

3대중량이 단 하루도 500 미만으로 내려가지 않도록, 운동 키트를 사용하는 순서의 경우의 수를 모두 찾기

 

결국 중량의 변화는 (K + 키트로 인한 중량 증가량) 이므로, 입력받은 배열에서 미리 K를 빼 주었다.

중량 변화가 음수일 경우 500 미만으로 내려가는 것 이므로, 중량 변화량이 N일동안 계속해서 양수인 경우의 수를 찾으면 된다.

 

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class 근손실_18429 {

   

    // 결과 저장할 변수

    static int cnt = 0;

    public static void main(String[] args) throws Exception {

       

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        // N, K 입력받기

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(st.nextToken());

        // 운동키트 입력받기

        st = new StringTokenizer(br.readLine());

        int kit[] = new int[N];

        for(int i = 0; i < N; i++) {

            kit[i] = Integer.parseInt(st.nextToken()) - K;

        }

        // 방문체크 배열

        boolean visited[] = new boolean[N];

        // 탐색 진행

        backTraking(0, 0, N, visited, kit);

        // 결과 출력

        System.out.println(cnt);

       

        br.close();

    }

    public static void backTraking(int depth, int sum, int N, boolean visited[], int kit[]) {

       

        // 최대 깊이에 도달했을 경우 cnt + 1 후 리턴

        if(depth == N) {

            cnt += 1;

            return;

        }

        // 방문 안했고 500이상이면 탐색 진행

        for(int i = 0; i < N; i++) {

            if(visited[i] == false && sum + kit[i] >= 0) {

                visited[i] = true;

                backTraking(depth + 1, sum + kit[i], N, visited, kit);

                visited[i] = false;

            }

        }

    }

}

 

백트래킹으로 해결했다.