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

목차

문제 : 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++;
        }
    }
}