[Softeer]택배 마스터 광우

 

※소프티어 문제를 풀면서 의식의 흐름에 따라 일기 형식으로 작성한 글이다. 답안 로직에 대한 설명은 없다.

 

https://softeer.ai/practice/6273

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

 

위 문제는 문제를 이해하는데 시간이 오래 걸렸다....

문제의 핵심은 [ 레일의 순서를 조작 ] 하는 것이었다.

택배일을 하는데,, 레일의 순서를 조작해서 1번 레일부터 일하는데 가장 적게 들수있게 레일의 순서를 조작하는것!

 

레일의 개수 범위가 3 ≤ N ≤ 10 이기 때문에, 

레일의 순서를 변경한 모든 경우의 수를 구하는 경우가 가능해 보였다.

 

오름차순으로 다음 순번을 구하는 문제는 백준에서 풀어본 문제이다.

백준 [10972] [다음 순열] 문제

https://www.acmicpc.net/problem/10972

다음 순열을 구하는 함수 명칭을 뭐라고 했더라 기억이 안나서 그냥 "내림차순가자" 라는 의미로 함수를 만들었다..

 

오름차순으로 정렬한 뒤, 오름차순 순서를 하나씩 높여서 모든 경우의 수를 구하면 된다.

레일 순서가 가능한 모든 경우의 수마다 광우가 택배로 일하는 횟수 k에 가능한 무게중,최소 무게를 구했다.

 

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

public class Main {

    static boolean goDescending(int[] c){
        int i = c.length - 1;
        while(i > 0 && c[i-1] > c[i]){
            i--;
        }
        if(i==0){
            return false;
        }
        int j = c.length - 1;
        while(j>0 && c[i-1] > c[j]){
            j--;
        }
        int temp = c[i-1];
        c[i-1] = c[j];
        c[j] = temp;

        j = c.length-1;
        while(i<j){
            temp = c[i];
            c[i] = c[j];
            c[j] = temp;
            i++;
            j--;
        }
        return true;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] a = new int[n];
        int[] c = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(st.nextToken());
            c[i] = i;
        }

        int ans = -1;
        do{
            int start = c[0];
            int sumM = 0;
            for(int i=0; i<k; i++){
                int curM = 0;
                while(curM <= m){
                    if(curM + a[c[start]] <= m){
                        curM += a[c[start]];
                        start++;
                        start %= n;
                    }else{
                        break;
                    }
                }
                sumM += curM;
            }
            if(ans > sumM || ans == -1){
                ans = sumM;
            }
        }while(goDescending(c));

        bw.write(String.valueOf(ans));
        bw.close();
    }

}