풀이 아이디어

키트를 사용해 생긴 중량 증가량에 매일 감소하는 감소량 k를 미리 빼고 배열에 저장한다.
운동 키트를 사용하는 순서가 있을 때 총합 중량 변화량 sumWeight=0으로 두고
중량 500 이상이 유지되는 경우의 수, 즉 sumWeight>0을 유지하는 경우의 수를 DFS 재귀함수로 구한다.
DFS의 depth를 설정해줘서 마지막 키트까지 사용하면 depth=n이 되고
중량 변화량이 0보다 크거나 같으면 가능한 경우의 수이므로 경우의 수를 저장한 caseCount를 +1해준다.
경우의 수를 따지는 중간에 sumWeight<0이 되는 경우 종료조건을 설정해 백트래킹을 구현한다.

풀이 코드

import java.io.*;
import java.util.*;

public class _18429 {
    static int sumWeight = 0;
    static int caseCount = 0;
    public static void main(String[] args) throws IOException{
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] changeWeight = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            // 키트 증가량 - k해서 배열에 저장
            changeWeight[i] = Integer.parseInt(st.nextToken()) - k;
        }

        // 재귀적으로 모든 경우의 수를 탐색
        findCase(changeWeight, new boolean[n], n,0);

        System.out.println(caseCount);
    }

    public static void findCase(int[] changeWeight, boolean[] visited, int n, int depth){
        if(sumWeight < 0){
            return;
        }
        if(sumWeight >= 0 && depth == n){
            caseCount++;
            return;
        }

        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                sumWeight += changeWeight[i];
                findCase(changeWeight, visited, n, depth+1);
                visited[i] = false;
                sumWeight -= changeWeight[i];
            }
        }
        return;
    }
}