소프티어 택배 마스터 광우

Softeer 택배 마스터 광우 바로가기

문제 설명

특정 무게만 옮길 수 있는 레일에서 택배가 온다.

레일 순서대로 택배를 받아서 처리할건데 M무게 만큼까지만 광우는 택배를 담을 수 있다.

레일 순서를 조작해서 K번 일을 할건데 최소 무게로 택배를 옮길때의 무게를 출력해라.

접근 방식

딱히 레일의 순서를 정하는 알고리즘이 없으므로 완탐하기로 결정, 순열을 돌려주어서 모든 레일 순서를 탐색해준다.

그리고 해당 레일 순서대로 큐에 넣어준 다음 큐에서 빼면서 조건에 맞게끔 반복을 계속 돌려준다.

코드

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


public class Main{
    static int[] rails;
    static int[] input;
    static boolean[] visit;
    
    static int N, M, K, minW;

    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());
        minW = M * K;

        st = new StringTokenizer(br.readLine(), " ");

        rails = new int[N];
        input = new int[N];
        visit = new boolean[N];

        for(int i = 0; i < N ; i++){
            rails[i] = Integer.parseInt(st.nextToken());
        }
        
        perm(0, 0);

        System.out.println(minW);

    }
    
    private static void perm(int start, int count){
        if(count == N){
            Queue<Integer> myQueue = new LinkedList<>();
            for(int v : input){
                myQueue.offer(v);
            }
            
            int kCount = 0;
            int sum = 0;
            int total = 0;

            while(true){
                sum += myQueue.peek();
                myQueue.offer(myQueue.poll());
                
                if(sum + myQueue.peek() > M){
                    kCount++;
                    total += sum;
                    sum = 0;
                }

                if(kCount == K) break;
            }

            minW = Math.min(total, minW);
            return;
        }

        for(int i = 0; i < N; i++){
            if(!visit[i]){
                visit[i] = true;
                input[count] = rails[i];
                perm(0, count + 1);
                visit[i] = false;
            }
        }

    }

}

Disscussion

완탐에다가 큐에서의 반복을 도니까 시간초과가 날 줄 알았는데 아니었따..

시간복잡도를 계산하는거를 좀 더 꼼꼼히 생각해야겠다