[Softeer] 택배 마스터 광우 (lv.3)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581 

Softeer

2021

---

import java.util.*;
import java.io.*;
 
 
public class Main {
    public static int N, M, K, answer;
    public static int[] arr;
    public static boolean[] vtd;
    public static void solve(int[] parcel) {
        int idx = 0;
        int total = 0;
        for(int i = 0; i < K; i++) {
            int sum = 0;
            for(int j = idx; ;j++) {
                if(sum + parcel[j%N] > M) {
                    idx = j;
                    break;
                }
                else sum += parcel[j%N];
            }
            total += sum;
        }
        answer = Math.min(answer, total);
    }
 
    public static void comb(int cnt, int[] p) {
        if(cnt == N) {
            solve(p);
            return;
        }
 
        for(int i = 0; i < N; i++) {
            if(!vtd[i]) {
                vtd[i] = true;
                p[cnt] = arr[i];
                comb(cnt+1, p);
                vtd[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        answer = 987654321;
 
        arr = new int[N];
        vtd = new boolean[N];
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int[] p = new int[N];
        comb(0, p);
 
        System.out.println(answer);
    }
}