본문 바로가기
PS/BOJ

[자바] 백준 1092 - 배 (java)

by Nahwasa 2023. 3. 14.

목차

    문제 : boj1092

     

     

    필요 알고리즘

    • 그리디 알고리즘, 정렬
      • 규칙성을 찾아 매번 최선의 방식으로 진행하는 그리디로 풀 수 있는 문제이다. 보통 그리디 태그는 정렬도 필요한 경우가 많다. 

    ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

     

     

    풀이

      풀고나서 다른 사람들 코드를 보니 아예 다른 로직들이 보여서 좀 당황스러웠다. 보통 크레인 무게 제한 내림차순, 박스 무게 내림차순으로 정렬한 후, 각 크레인에 가능한 박스를 넣는 시뮬레이션 느낌으로 푼 것 같다.

     

      시간복잡도 면에서 내가 푼 방식이 더 나은 것 같아서 (O(NM)) 따로 다른 풀이로도 풀어보진 않았다. 이하 풀이는 내가 푼 방식의 풀이이다.

     

      이 문제에서 아무리 최적으로 움직여도 ⌈ M / N ⌉분 보다 빠르게 작업할 수 없다(모든 박스의 무게가 1이라고 해도 아무튼 N개씩 옮겨야 하므로).

    그렇다면, 어떤 방법으로든, 'X분이 주어졌을 때 모든 박스를 옮길 수 있음'을 알 수 있다면, X를 M / N ⌉ 부터 M 까지 증가시켜가면서 X분 이내에 박스를 옮길 수 있을 때 X를 출력해주면 그게 최선의 시간이 된다. 이 때 박스를 옮기는걸 아는게 O(N)이 걸린다면, O(N(M-M/N) = O(NM)에 답을 구할 수 있다.

     

      그럼 이제 'X분이 주어졌을 때 모든 박스를 옮길 수 있음'을 어떻게 알 수 있는지 알아보자. 크레인의 무게제한을 arr에 입력받았다. 그리고 arr을 오름차순으로 정렬하고, N 크기의 cnt[] 배열을 만들었다. cnt[i]는 각 박스를 입력받으면서 해당 박스의 무게를 들 수 있는 가장 무게제한이 낮은 크레인이 arr[i] 일 경우 cnt[i]를 1 증가해줬다. 예를들어 아래의 경우

    5
    1 3 5 7 9
    7
    1 1 2 3 3 7 8

     

      arr 와 cnt는 다음과 같다. arr[0]에 '1'짜리 박스 2개, arr[1]에 '2'짜리 박스 1개와 '3'짜리 박스 2개, arr[2]는 없고, arr[3]과 arr[4]는 각각 '7'과 '8'짜리 박스가 카운팅된다.

     

      그럼 이제 arr배열도 필요없고 박스의 무게들도 필요없다. cnt 배열만 보면 된다. 여기서 알 수 있는점은 인덱스가 더 낮은 곳에 있는 cnt 값은 인덱스가 더 높은 곳으로 이동이 가능하다는 점이다(인덱스가 더 낮은 곳이 더 낮은 무게의 박스이므로 당연히 더 무게제한이 높은 크레인으로 들 수 있다.)

     

      그렇다면 X = ⌈ M / N ⌉ 부터 M 까지라고 했을 때, cnt[i]가 X 이하라면 무시하면 되고, X 이상이라면 cnt[i]-X 만큼을 cnt[i+1]로 이동시켜주면 된다. 위의 예시라면 X가 처음에 ⌈ 7 / 5 ⌉ = 2 이므로, 아래와 같이 될 것이다.

     

      이런식으로 캐리를 옮기면서, 최종적으로 cnt 배열의 끝까지 왔을 때 값이 X 이하라면 X분으로 옮기는게 가능한 경우임을 알 수 있다.

    while (true) {
        int tmp = cnt[0];
        for (int i = 0; i < n-1; i++) {
            if (tmp <= limit) {	// limit이 X에 해당한다. X 이하라면 무시한다.
                tmp = cnt[i+1];
                continue;
            }
            int gap = tmp - limit;
            tmp = cnt[i+1] + gap;	// X초과라면 cnt[i]-X 만큼 cnt[i+1]에 더한다.
        }
        if (tmp <= limit) {	// N개를 전부 본 이후에 최종적으로 X번 이하라면
            System.out.println(limit);	// 해당 X가 최선의 답이므로 출력하고 끝낸다.
            return;
        }
        limit++;	// 못찾았다면 X를 증가시켜준다.
    }

     

      참고로 무한루프인 이유는 어차피 불가능한 경우는 아래 코드 부분에서(박스 무게가 최대 무게 제한의 크레인보다 큰 경우 불가능한 경우이다.) 걸러줬으므로, 무조건 X=M 이하로 종료됨이 보장되기 때문이다.

    if (i == n-1) {
        System.out.println(-1);
        return;
    }

     

     

    코드 : github

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.StringTokenizer;
    
    public class Main {
    
        private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    
        public static void main(String[] args) throws Exception {
            new Main().solution();
        }
    
        public void solution() throws Exception {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(arr);
    
            int[] cnt = new int[n];
            int k = Integer.parseInt(br.readLine());
            int limit = k/n + (k%n!=0 ? 1 : 0);
            st = new StringTokenizer(br.readLine());
            while (k-->0) {
                int cur = Integer.parseInt(st.nextToken());
                for (int i = 0; i < n; i++) {
                    if (arr[i] >= cur) {
                        cnt[i]++;
                        break;
                    }
                    if (i == n-1) {
                        System.out.println(-1);
                        return;
                    }
                }
            }
    
            while (true) {
                int tmp = cnt[0];
                for (int i = 0; i < n-1; i++) {
                    if (tmp <= limit) {
                        tmp = cnt[i+1];
                        continue;
                    }
                    int gap = tmp - limit;
                    tmp = cnt[i+1] + gap;
                }
                if (tmp <= limit) {
                    System.out.println(limit);
                    return;
                }
                limit++;
            }
        }
    }

     

    댓글