[Softeer] Lv3. 택배마스터 광우 (Java)

1. 문제

• 문제 링크 : Lv3. 택배마스터 광우
• 주제 : 완전탐색, 백트래킹

---

2. 풀이 과정 및 정리

이 문제에서는 레일을 어떤 순서로 돌아서 최소한의 무게로 일할 수 있는지 찾아야한다. 

 

위의 그림과 같이 레일을 돌면서 바구니 무게를 초과하기 전까지는 무조건 1번으로 시행되어야 한다.

 

이는 딱히 규칙성이나 공식을 찾을 수 없다.

그래서 내가 선택한 방식은 완전탐색을 하여 레일의 순서를 모두  구했다.

이를 구하기 위해서 아래와 같이 백트래킹 방식으로 순서를 구했다.

static void dfs(int count, int[] result) {
    if(count == n) { //순서가 정해졌을 경우
        int w = getWeight(result);
        minWeight = Math.min(w, minWeight);
        return;
    }

    //백트래킹 적용
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            visited[i] = true;
            result[count] = rails[i];
            dfs(count+1, result);
            visited[i] = false;
        }
    }
}

 

처음에는 시간초과를 걱정했지만 레일의 수는 최대 50개이므로 문제없이 풀렸다.

---

3. 코드

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

public class Main {

    static int n, m, k;
    static int[] rails;
    static boolean[] visited;
    static int minWeight = Integer.MAX_VALUE;

    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());

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

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

    // 레일의 순서정하기
    static void dfs(int count, int[] result) {
        if(count == n) {
            int w = getWeight(result);
            minWeight = Math.min(w, minWeight);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[count] = rails[i];
                dfs(count+1, result);
                visited[i] = false;
            }
        }
    }

    // 들어야하는 무게 구하기
    static int getWeight(int[] result) {
        int r = 0;
        int idx = 0;
        for(int i = 0; i < k; i++) {
            int weight = 0;
            while(weight + result[idx] <= m) {
                weight += result[idx];
                idx = idx + 1 == n ? 0 : idx+1;
            }
            r += weight;
        }
        return r;
    }
}