[Algorithm] Softeer_택배 마스터 광우 (JAVA)

2025. 5. 16. 20:47·Algorithm

📝문제

https://softeer.ai/practice/6273

 

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

 

softeer.ai

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.

레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)

총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.

제약조건

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

입력형식

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

출력형식

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


💡풀이

문제 유형

브루트포스

 

걸린 시간

55분

 

시간 복잡도

O(N!)

 

풀이 방법 도출

레일의 최대개수가 10개까지이므로 10!을 해도 120이다.

레일의 순서를 만들 수 있는 모든 경우의 수를 찾아 최소 택배 무게를 탐색한다.

 

모든 레일 배열에 대해 K번까지 M을 넘지 않는 경우의 합을 계산해주었다.

 

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

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int N, M, K;
    static int[] arr;
    static int[] weight;
    static boolean[] visited;
    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];
        visited = new boolean[N];

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

        weight = new int[N];
        dfs(0);

        System.out.println(answer);
    }
    public static void dfs(int idx){
        if(idx == N){
            int cur_idx = 0;
            int cnt = 0;
            int sum = 0;
            int total = 0;

            while(cnt < K){
                cur_idx = cur_idx%N;
                if(sum + weight[cur_idx] > M){
                    cnt++;
                    total += sum;
                    sum = 0;
                }
                sum += weight[cur_idx];
                cur_idx++;
            }

            answer = Math.min(answer, total);
        }
        
        for(int i = 0; i < N; i++){
            if(!visited[i]){
                weight[idx] = arr[i];
                visited[i] = true;
                dfs(idx+1);
                visited[i] = false;
            }
        }
    }
}

🤔Review

기업 코테스러운 문제다. 이유: 뭔가 규칙 있을 거 같은데 없음, 뭔가 알고리즘 써야 풀릴 거 같은데 그냥 완탐임

 

'Algorithm' 카테고리의 다른 글

[Algorithm] Softeer_출퇴근길 (JAVA) DFS, BFS  (0) 2025.05.17
[Algorithm] Softeer_성적 평균 (JAVA)  (0) 2025.05.16
[Algorithm] Softeer_CPTI (JAVA)  (5) 2025.05.16
[Algorithm] 백준_주유소_13305번 (JAVA)  (0) 2025.05.15
[Algorithm] 백준_소수의 연속합_1644번 (JAVA) 에라토스테네스의 체  (3) 2025.05.14
'Algorithm' 카테고리의 다른 글
  • [Algorithm] Softeer_출퇴근길 (JAVA) DFS, BFS
  • [Algorithm] Softeer_성적 평균 (JAVA)
  • [Algorithm] Softeer_CPTI (JAVA)
  • [Algorithm] 백준_주유소_13305번 (JAVA)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (147)
      • Front-end (0)
      • Back-end (11)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (80)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      개발자취업
      코딩테스트준비
      TypeScript
      99클럽
      항해99
      티스토리챌린지
      오블완
      Til
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] Softeer_택배 마스터 광우 (JAVA)
    상단으로

    티스토리툴바