[소프티어] 택배 마스터 광우 자바 풀이 dfs 쉽게 접근하기

[소프티어] 택배 마스터 광우 자바 풀이 dfs 쉽게 접근하기

 

 

 

https://softeer.ai/practice/6273

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

 

 

 

 

언어별 시간/메모리

언어시간메모리

JavaScript	2초	256MB
C	2초	256MB
C++	2초	256MB
Java	2초	256MB
Python	2초	256MB

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 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

 

 

 

 

 

핵심설명

순서 짜는게 중요합니다

무게 합 뭐시기 다 무시하시고

순서만 짜세요 일단 순서만

순서만 짜서 출력해보세요

calWeight 무시하시고 dfs함수부터 구현해보신 다음에

순서를 모조리 출력해보고

그다음 calWeight를 구현하세요

 

1. DFS로 레일의 순서를 모조리 구해주자

2. 하나하나의 순서에 대해 바구니 무게제한과 횟수를 적용한 최소합계를 구해주자

 

 

전체코드

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

public class Main {

    public static int n, m, k;
    public static int line[];
    public static int v[];
    public static int dap = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

        dfs(new int[n], 0);

        // bw.newLine();
        bw.write(String.valueOf(dap) + "\n");
        bw.flush();
        bw.close();
    }

    // 첫번째 미션 : 레일 순서 정하기
    static void dfs(int[] railOrder, int count) {

//        for(int i=0; i<railOrder.length; i++){
//            System.out.println(i + " " + railOrder[i] + " " + count);
//        }
//        System.out.println();

        if(count == n) {    // railOrder 가 꽉 채워져서 n개의 레일의 순서가 모두 정해졌다면
            int w = calWeight(railOrder);   // 바구니제한m과 k횟수로 최소무게 구하러 가자
            dap = Math.min(w, dap);
            return;
        }

        for(int i = 0; i < n; i++) {
            if(v[i] == 0) {
                v[i] = 1;
                railOrder[count] = line[i];
                dfs(railOrder, count+1);
                v[i] = 0;
            }
        }
    }

    // 두번째 미션 : 정해진 레일 순서에 대해서, 바구니제한m과 k횟수로 최소무게 합 구하기
    static int calWeight(int[] railOrder) {
        int sum = 0;
        int railNum = 0;
        for(int i = 0; i < k; i++) {    // k번 시행횟수 안에서
            int checkWeight = 0;        // 일회당 옮겨질 무게 변수 초기화해주고
            while(checkWeight + railOrder[railNum] <= m) {  // 무게제한m보다 작으면
                checkWeight += railOrder[railNum];          // 더해주고
                // railNum = (railNum + 1 == n) ? 0 : railNum+1;
                if(railNum+1 == n){     // 현재 레일이 마지막이었다면 (=다음레일이 없다면)
                    railNum = 0;        // 첫번째 레일로 다시 돌아가기 위해 변수 초기화
                }else{                  // 현재 레일이 중간 레일이라면
                    railNum++;          // 다음 레일로 가기 위한 변수 +1
                }
            }
            // 1회 안에 바구니에 담을 수 있는 무게 전부 담았다면 sum에 더해주자
            sum += checkWeight;
        }
        return sum;
    }
}