https://softeer.ai/practice/info.do?idx=1&eid=581

문제

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.

레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)

총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.

제약조건

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

입력형식

첫째 줄에는 레일의 개수 N, 택배 바구니의 무게 M, 일의 시행 횟수 K가 주어진다. 그 다음 줄에는 Ni개의 택배 레일의 전용 무게가 주어진다. (택배 바구니는 무조건 택배보다 작은 경우는 없다.)

출력형식

출력으로는 광우가 일 해야하는 최소한의 택배 무게를 출력한다.

입출력 예제

• 입력예제1

5 20 4
5 8 10 19 7

• 출력예제1

54

레일의 개수가 5개이고 택배 바구니의 무게를 20, 일을 시행해야 하는 횟수를 4번 이라고 했을 때, 레일의 순서가 | 5 | 8 | 10 | 19 | 7 | 이 된다면 총 4번 수행 했을 때 답은 62가 된다.

1번 (5+8)
2번 (5+8) + (10)
3번 (5+8) + (10) + (19)
4번 (5+8) + (10) + (19) + (7+5+8) = 62

하지만 최적의 순서는 | 5 | 10 | 8 | 19 | 7 | 이 된다.

1번 (5+10)
2번 (5+10) + (8)
3번 (5+10) + (8) + (19)
4번 (5+10) + (8) + (19) + (7+5) = 54

• 입력예제2

9 25 50
1 21 2 22 3 23 4 24 10

• 출력예제2

772

Solution

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

public class Main
{
    static boolean[] VISIT = new boolean[11];
    static int[] MATRIX = new int[11];
    static int result = 99999999;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] railData = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            railData[i] = Integer.parseInt(st.nextToken());
        }

        DFS(0, N, M, K, railData);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static void DFS(int count, int N, int M, int K, int[] railData) {
        if (count == N) {
            int idx = 0;
            int bucket = 0;
            int sumOfData = 0;

            for (int work = 0; work < K; work++) {
                while (MATRIX[idx] + bucket <= M) {
                    bucket += MATRIX[idx];
                    idx = (idx + 1) % N;
                }
                sumOfData += bucket;
                bucket = 0;
            }
            result = Math.min(sumOfData, result);
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!VISIT[i]) {
                VISIT[i] = true;
                MATRIX[count] = railData[i];
                DFS(count + 1, N, M, K, railData);
                VISIT[i] = false;
            }
        }
    }
}

N의 최대값은 10이다. 즉 이런 경우엔 완전탐색이 장땡이다.