[소프티어] 개인정보 수집 유효기간 - Java

문제

https://softeer.ai/class/devcrew/study/resource/detail/description/6273?id=155&resourceId=83

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

 

---

 

문제 개요

광우는 택배 상하차 아르바이트에서 최소한의 무게로 일을 하기 위해 택배 레일의 순서를 최적화하려고 합니다. 각 레일은 특정 무게 전용이며, 주어진 순서대로 택배를 옮길 때 바구니의 무게를 초과하지 않도록 담아야 합니다. 이 작업을 정해진 횟수만큼 반복해야 하며, 최소한의 총 무게를 들기 위해 레일 순서를 조정해야 합니다.

 

접근 방법

1. 순열 생성:
   • 모든 레일의 순서를 변경할 수 있으므로, 레일 배열의 모든 순열을 생성하여 시도합니다. N이 10이기 때문에 가능하다고 판단하였습니다.
   • 이를 위해 백트래킹을 활용합니다.
2. 각 순열의 무게 계산:
   • 생성된 순열을 기준으로 K번 작업을 수행할 때의 총 무게를 계산합니다.
   • 작업은 순서대로 진행되며, 바구니에 담을 수 있는 무게(M)를 초과하지 않는 범위 내에서만 택배를 담습니다.
3. 최소 무게 갱신:
   • 계산된 총 무게를 기존 최소 무게(min)와 비교하여 더 작은 값으로 갱신합니다.

 

코드

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

public class Main {

    static int[] arr;
    static int min = Integer.MAX_VALUE;
    static int N, M, K;

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

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(new ArrayList<>(), new boolean[N]);
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    public static void dfs(List<Integer> list, boolean[] v) {
        if (list.size() == N) {
            min = Math.min(getMin(list), min);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!v[i]) {
                v[i] = true;
                list.add(arr[i]);
                dfs(list, v);
                list.remove(list.size() - 1);
                v[i] = false;
            }
        }
    }

    public static int getMin(List<Integer> list) {
        int n = 0;
        int idx = 0;
        for(int i=0; i<K; i++) {
            int w = 0;
            while(w + list.get(idx) <= M) {
                w += list.get(idx);
                idx++;
                if(idx >= N) idx = 0;
            }
            n += w;
        }
        return n;
    }
}