백준 1092 배

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

무게 제한이 있는 N개의 크레인과, M개의 박스가 존재한다.

각 크레인은 1분에 1개의 박스씩만을 배에 실을 수 있으며 무게 제한보다 무거운 박스는 옮길 수 없다.

모든 박스를 옮기는 데 걸리는 시간을 출력하는 문제이다.

크레인 개수인 N은 최대 50이고 박스 개수인 M은 최대 10,000개이다.

가장 효율적으로 모든 박스를 실어 나르기 위해선, 1분마다 각 크레인의 무게 제한 내에서 실을 수 있는 가장 무거운 박스를 실어야 한다.

그래서 먼저 크레인과 박스를 내림차순으로 정렬하였다.

풀이에 사용된 테스트케이스를 통해 풀이과정을 생각해 보자.

4
30 25 20 15
10
30 29 28 27 24 23 22 20 19 18

내림차순으로 어차피 정렬할 것이므로 내림차순인 상태로 입력을 하도록 하였다.

풀이의 핵심인 매 분마다 각 크레인이 실을 수 있는 가장 무거운 박스를 싣는다 라는 것에 따라 풀이해 보자.

1분 - 제한 30인 크레인은 30을, 제한 25인 크레인은 24를, 제한 20인 크레인은 20을, 제한 15인 크레인은 옮기지 못함. - 박스 3개 처리

2분 - 제한 30인 크레인은 29를, 제한 25인 크레인은 23을, 제한 20인 크레인은 19를, 제한 15인 크레인은 X - 박스 3개 처리

3분 - 제한 30인 크레인은 28을, 제한 25인 크레인은 22를, 제한 20인 크레인은 18을, 제한 15인 크레인은 X - 박스 3개 처리

4분 - 제한 30인 크레인은 27을, 나머지 크레인은 옮길 박스가 없다.

위와 같이 진행된다.

대략적인 풀이 방법을 생각하였고, 이를 어떻게 구현할지 설계한다.

내가 사용한 아이디어는 다음과 같다.

1. 박스는 내림차순이므로, 각 크레인에 대해 옮길수 있는 인덱스를 준비한다.
   ex) 30 크레인은 0번 인덱스의 박스부터 가능, 25 크레인은 4번 인덱스(24)의 박스부터 가능, 20 크레인은 7번 인덱스(20)의 박스부터, 15 크레인은 옮길 수 있는 박스가 없으므로 인덱스 10. - {0, 4, 7, 10}

2. 각 박스의 처리 여부를 나타내는 Boolean 배열을 선언

3. 남아 있는 박스가 0개가 될 때까지 while문을 통해 각 크레인 인덱스를 증가시키며 박스를 처리함.
   인덱스 - {0, 4, 7, 10}

3-1) 앞의 세 크레인으로 0번, 4번, 7번 인덱스의 박스를 처리함.
인덱스 - {1, 5, 8, 10}

3-2) 앞의 세 크레인으로 1번, 5번, 8번 인덱스의 박스를 처리함.
인덱스 - {2, 6, 9, 10}

3-3) 앞의 세 크레인으로 2번, 6번, 9번 인덱스의 박스를 처리함.
인덱스 - {3, 7, 10, 10}

3-4) 0번 인덱스의 크레인으로 3번 인덱스의 박스를 처리함. 모든 박스 처리했으므로 종료.

인덱스를 증가시키되, 이미 처리된 박스에 도착하면 해당 박스를 건너뛰도록 구현해야 함.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val cranes = readLine().split(' ').map{it.toInt()}.sortedDescending()
    val M = readLine().toInt()
    val boxes = readLine().split(' ').map{it.toInt()}.sortedDescending()

    if(cranes.maxOrNull()!! < boxes.maxOrNull()!!){
        print(-1)
        return@with
    }

    var remain = M
    val complete = BooleanArray(M){false}
    val cIndexes = IntArray(N){ M }

    var ptr = 0
    // cIndexes - i번째 크레인은 i번째 박스부터 이후 모든 박스를 나를 수 있음을 의미(박스는 내림차순이므로)
    for(i in boxes.indices){
        while(ptr < N && cranes[ptr] >= boxes[i]){
            cIndexes[ptr++] = i
        }
        if(ptr == N) break
    }

    var time = 0
    while(remain > 0){
        for(i in cIndexes.indices){
            // 이미 처리된 상자인 경우 건너뛰기
            while(cIndexes[i] < M && complete[cIndexes[i]]){
                cIndexes[i]++
            }
            
            // 처리안된 박스 발견 시 처리 표시 + 인덱스 증가 + 남은 박스개수 감소
            if(cIndexes[i] < M && !complete[cIndexes[i]]){
                complete[cIndexes[i]] = true
                cIndexes[i]++
                remain--
            }
        }
        time++
    }

    print(time)
}