[소프티어] 택배 마스터 광우

https://softeer.ai/practice/6273

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

 

이 문제는 레일의 순서를 임의로 변경 가능하기 때문에 각각의 경우의 수를 모두 찾아서 그 중 최소값을 찾는 문제라고 생각했고, 백트래킹을 사용하면 된다고 판단했다.

 

백트래킹을 사용하기 전 시간복잡도를 먼저 알아보자면

레일의 개수는 최대 10개이고, 일의 시행 횟수는 최대 50이기 때문에 worst case 여도 10 x 50 = 500번 정도 이기 때문에 

충분히 O(n^2) 작업도 가능하다.

 

1. 만들어질 수 있는 모든 레일의 경우의 수를 구한다.

2. 각각의 경우 마다 광우가 들 수 있는 택배의 무게를 구한다.

3. 각 경우의 수마다 구해진 택배 무게 중 최소값을 찾는다. 

---

1. 레일의 모든 경우의 수 탐색 및 택배 최소 무게 찾기

백트래킹을 통해 모든 경우의 수를 찾는다.

// bfs(0, new int[n]) <- bfs 초기값
private static void bfs(int count, int[] boxSeq) {
        if (count == n) {
            int w = calculateWeight(boxSeq);
            minWeight = Math.min(minWeight, w);
            return;
        }

        for (int i=0; i<n; i++) {
            if(!visit[i]) {
                visit[i] = true;
                boxSeq[count] = boxs[i];
                bfs(count+1, boxSeq);
                visit[i] = false;
            }
        }
    }

---

2. 광우가 들 수 있는 택배의 총 무게를 구한다.

private static int calculateWeight(int[] boxSeq) {
    int result = 0;
    int idx = 0;

    for (int t=0; t<k; t++) {
        int curWeight = 0;

        while (curWeight + boxSeq[idx] <= m) {
            curWeight += boxSeq[idx];
            idx = idx + 1 == n ? 0 : idx + 1;
        }
        result += curWeight;
    }

    return result;
}

---

전체 코드

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

public class Main {

    private static int n,m,k,minWeight = 987654321;
    private static int[] boxs;
    private static boolean[] visit;
    
    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());

        boxs = new int[n];
        visit = new boolean[n];

        st = new StringTokenizer(br.readLine()," ");
        for (int i=0; i<n; i++) {
            boxs[i] = Integer.parseInt(st.nextToken());
        }

        bfs(0, new int[n]);
        System.out.println(minWeight);
    }

    private static void bfs(int count, int[] boxSeq) {
        if (count == n) {
            int w = calculateWeight(boxSeq);
            minWeight = Math.min(minWeight, w);
            return;
        }

        for (int i=0; i<n; i++) {
            if(!visit[i]) {
                visit[i] = true;
                boxSeq[count] = boxs[i];
                bfs(count+1, boxSeq);
                visit[i] = false;
            }
        }
    }

    private static int calculateWeight(int[] boxSeq) {
        int result = 0;
        int idx = 0;
    
        for (int t=0; t<k; t++) {
            int curWeight = 0;
            
            while (curWeight + boxSeq[idx] <= m) {
                curWeight += boxSeq[idx];
                idx = idx + 1 == n ? 0 : idx + 1;
            }
            result += curWeight;
        }
        
        return result;
    }
}