[Softeer - Lv. 3] 택배 마스터 광우

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

순열 조합을 통해 최소 작업량을 구하는 문제이다.

[문제 제약 조건]

Java

2초

256MB

 

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

 

[입력형식]

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

 

[출력형식]

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

 

입력	5 20 4 5 8 10 19 7
출력	54

---

1. 입력

우선 순열 조합과 작업량 비교를 위한 클래스 단위 변수 선언을 한다.

static int n, m, k;
static int[] rails;
static int minW = Integer.MAX_VALUE;

이후 입력 받기

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
k = Integer.parseInt(input[2]);

String[] b = br.readLine().split(" ");
rails = new int[n];
for(int i = 0; i < n; i++){
	rails[i] = Integer.parseInt(b[i]);
}

 

2. 순열 조합

각 순서에 대한 조합을 구성하기 위해 순열 함수를 선언한다.

static void permute(int d, int[] order, boolean[] visited){
	if(d == n){
    	calc(order);
        return;
    }
    for(int i = 0; i < n; i++){
    	if(!visited[i]){
        	visited[i] = true;
            order[d] = rails[i];
            permute(d + 1, order, visited);
            visited[i] = false;
        }
    }
}

 

depth가 최고차(n)까지 도달하면 더 이상 조합할 수 없으므로 작업량 계산.

아니면 반복문을 통해 그 안에서 조합을 재귀적으로 생성한다.

 

3. 작업량 계산

static void calc(int[] order){
    int total = 0;
    int count = 0;

    for(int i = 0; i < n; i++){
        int cur = order[i];
        if(count == k){
            break;
        }
        for(int j = i; j < k*n; j++){
            int idx = (j+1)%n;
            if(cur + order[idx] > m){
                i = idx -1;
                break;
             } else {
                cur += order[idx];
             }
        }
        total += cur;
        count++;
    }

    if(count == k){
        minW = Math.min(total, minW);
    }
}

순서대로 가져가야 하므로 각 레일에 대해 0번째부터 작업량 계산을 진행한다.

계속 틀렸던 부분이 현재 작업량에 더해줄 order[idx]에 대한 계산이었는데 for 문 특성상 i는 자동적으로 1씩 증가하기 때문에 i = idx -1로 해주어야 한다.

---

전체 코드

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

public class Main {
    static int n, m, k;
    static int[] rails;
    static int minW = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        k = Integer.parseInt(input[2]);

        String[] b = br.readLine().split(" ");
        rails = new int[n];
        for(int i = 0; i < n; i++){
            rails[i] = Integer.parseInt(b[i]);
        }

        permute(0, new int[n], new boolean[n]);
        System.out.print(minW);
    }

    static void permute(int d, int[] order, boolean[] visited){
        if(d == n){
            calc(order);
            return;
        }
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                visited[i] = true;
                order[d] = rails[i];
                permute(d + 1, order, visited);
                visited[i] = false;
            }
        }
    }

    static void calc(int[] order){
        int total = 0;
        int count = 0;

        for(int i = 0; i < n; i++){
            int cur = order[i];
            if(count == k){
                break;
            }
            for(int j = i; j < k*n; j++){
                int idx = (j+1)%n;
                if(cur + order[idx] > m){
                    i = idx -1;
                    break;
                } else {
                    cur += order[idx];
                }
            }
            total += cur;
            count++;
        }

        if(count == k){
            minW = Math.min(total, minW);
        }
    }
}

 

결과