[Algorithm] Softeer_택배 마스터 광우 (JAVA)

📝문제

https://softeer.ai/practice/6273

Softeer - 현대자동차그룹 SW인재확보플랫폼

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

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

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

제약조건

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

입력형식

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

출력형식

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

---

💡풀이

문제 유형

브루트포스

 

걸린 시간

55분

 

시간 복잡도

O(N!)

 

풀이 방법 도출

레일의 최대개수가 10개까지이므로 10!을 해도 120이다.

레일의 순서를 만들 수 있는 모든 경우의 수를 찾아 최소 택배 무게를 탐색한다.

 

모든 레일 배열에 대해 K번까지 M을 넘지 않는 경우의 합을 계산해주었다.

 

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

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int N, M, K;
    static int[] arr;
    static int[] weight;
    static boolean[] visited;
    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());//레일의 개수
        M = Integer.parseInt(st.nextToken());//택배 바구니의 무게
        K = Integer.parseInt(st.nextToken());//일의 시행 횟수

        arr = new int[N];
        visited = new boolean[N];

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

        weight = new int[N];
        dfs(0);

        System.out.println(answer);
    }
    public static void dfs(int idx){
        if(idx == N){
            int cur_idx = 0;
            int cnt = 0;
            int sum = 0;
            int total = 0;

            while(cnt < K){
                cur_idx = cur_idx%N;
                if(sum + weight[cur_idx] > M){
                    cnt++;
                    total += sum;
                    sum = 0;
                }
                sum += weight[cur_idx];
                cur_idx++;
            }

            answer = Math.min(answer, total);
        }
        
        for(int i = 0; i < N; i++){
            if(!visited[i]){
                weight[idx] = arr[i];
                visited[i] = true;
                dfs(idx+1);
                visited[i] = false;
            }
        }
    }
}

---

🤔Review

기업 코테스러운 문제다. 이유: 뭔가 규칙 있을 거 같은데 없음, 뭔가 알고리즘 써야 풀릴 거 같은데 그냥 완탐임