[BOJ] 백준 18429 근손실 (JAVA)

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

18429번: 근손실

 

🔍Solve

순조부의 전형적인 순열 문제입니다.

순열은 서로 다른 n개 중 r개를 택하며, 순서를 고려합니다. 주의해야 할 점은 n이 12를 넘어가면서(12!) 시간 복잡도가 폭발적으로 증가합니다. 

해당 문제는 n이 8까지이므로, 무리없이 돌릴 수 있었습니다.

 

운동 키트의 증량 증가량을 담은 배열을 선언하고 해당 배열을 순열 함수를 돌립니다.

permutation의 매개변수는 재귀를 돌리면서 현재까지 뽑은 순열의 개수를 나타내는 cnt, 뽑힌 순열의 값이 담겨있는 selected, 인덱스에 해당하는 숫자가 사용 중인지 관리하는 isSelected배열이 있습니다.

inductive part에서는 처음부터 키트배열의 길이만큼 탐색하며 배열의 모든 수를 현재 자리에 넣어봅니다.isSelected배열을 통해 기존 자리의 수들과 중복되는지 체크하고, 중복되지 않았다면 사용하고 다음 수를 뽑으러 갑니다. 마지막은 꼭 해당 자리를 false처리를 해주어야 합니다.

 

뽑힌 selected배열의 각 인덱스의 키트 운동량을 더해주고, K를 빼줍니다. 연산을 한 뒤의 값이 500보다 작으면 재귀를 빠져나옵니다.마지막 selected 인덱스까지 다 돌았다면 경우의 수를 1 증가시킵니다.

 

 

❗ Code

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

public class Main {
    //순열, 완탐, 백트래킹

    static int N; //운동 키트 개수
    static int K; //몇일 동안?
    static int[] kit; //운동 키트
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        kit = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            kit[i] = Integer.parseInt(st.nextToken());
        }
        permutaion(0, new int[N], new boolean[N]);
        System.out.println(count);
    }

    /**
     *
     * @param cnt           뽑은 개수
     * @param selected      뽑은 int형 배열
     * @param isSelected    각 자리가 뽑혔나 안뽑혔나 boolean배열
     */

    private static void permutaion(int cnt, int[] selected, boolean[] isSelected){
        //base part
        if(cnt==N){
//            System.out.println(Arrays.toString(selected));
            int mus = 500;
            for(int i=0;i<selected.length;i++){
                mus += selected[i];
                mus -= K;
                if(mus<500){
                    return;
                }
            }
            count++;
            return;
        }

        //inductive part
        for(int i=0;i<kit.length;i++){
            if(isSelected[i]) continue;

            selected[cnt] = kit[i];
            isSelected[i] = true;
            permutaion(cnt+1, selected, isSelected);
            isSelected[i] = false;
        }
    }
}