[ 백준 ] 18111 마인크래프트

Link | 18111번 문제 : 마인크래프트

Solution

현재 필드에 존재하는 최대 높이와 최소 높이 사이를 탐색하면서 가장 적절한 높이를 탐색하면 된다.

하나의 높이를 탐색하는데 현재 존재하는 높이들 중 최대 높이부터 탐색 해야 한다.

이는 사용할 수 있는 블럭에 제한이 있기 때문이다.

예를 들어 4칸의 필드가 있고 각각 4, 4, 4, 3의 높이를 가진다고 해보자.

이렇게만 보면 1초 동안 3의 높이를 4로 만드는 것이 가장 빠르다고 생각할 수 있다.

하지만 만약 현재 인벤토리에 블럭이 전혀 없다면 3을 4로 만들수가 없다.

그러므로 4들을 3으로 만들어서 6초의 시간이 걸린다.

이러한 상황을 고려하기 위해 4부터 탐색해야한다.

알고리즘은 다음과 같다.

Step 1. TreeMap을 초기화한다.
TreeMap의 Key 값은 필드에 존재하는 높이들이고 value는 높이의 개수이다.
이 때 향후 높이 탐색에서 높은 높이부터 탐색할 것이기 때문에 reverseOrder로 초기화한다.
4칸 필드의 높이들이 4, 4, 4, 3이면 TreeMap은 다음과 같다.
<4, 3> <3, 1>

TreeMap<Integer, Integer> sets = new TreeMap<>(Comparator.reverseOrder());

Step 2. 필드의 크기, 초기 블럭 갯수를 읽어준다,

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int row = Integer.parseInt(tokenizer.nextToken());
int col = Integer.parseInt(tokenizer.nextToken());
int initInven = Integer.parseInt(tokenizer.nextToken());

Step 3. 필드의 높이들을 읽으면서 최대, 최소를 계산한다.

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;

while (row-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    while (tokenizer.hasMoreTokens()) {
        int height = Integer.parseInt(tokenizer.nextToken());
        max = Math.max(max, height);
        min = Math.min(min, height);
        sets.put(height, sets.getOrDefault(height, 0) + 1);
    }
}

Step 4. 결과값 변수를 선언한다.
minTime은 동일 높이로 만드는 최소 시간이고 이때의 높이고 height이다.

int minTime = Integer.MAX_VALUE;
int height = 0;

Step 5. 최소 시간과 이 때의 높이를 계산한다.

int inven, time, blocks;
Loop:
for (int h = max; h >= min; h--) {                              // 최대 높이부터 검사
    inven = initInven;                                          // 인벤토리 초기화
    time = 0;                                                   // 시간 초기화
    for (Map.Entry<Integer, Integer> set : sets.entrySet()) {   // 필드 최대 높이부터 검사
        blocks = Math.abs(set.getKey() - h) * set.getValue();   // 필요한 블럭 수
        if (set.getKey() >= h) {                                // 필드 높이 >= h
            inven += blocks;                                    // Field to Inven
            time += 2 * blocks;                                 // 소요 시간 추가
        } else if (blocks <= inven) {                           // 필드 높이 < h
            inven -= blocks;                                    // Inven to Field
            time += blocks;                                     // 소요 시간 추가
        } else continue Loop;                                   // 불가능한 높이이면 skip
    }

    if (minTime > time) {                                       // 최소 시간 계산
        minTime = time;
        height = h;
    }
}

Code

GitHub Repository

private static final TreeMap<Integer, Integer> sets 
							= new TreeMap<>(Comparator.reverseOrder());

private static void solution() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int row = Integer.parseInt(tokenizer.nextToken());
    int col = Integer.parseInt(tokenizer.nextToken());
    int initInven = Integer.parseInt(tokenizer.nextToken());

    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    while (row-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        while (tokenizer.hasMoreTokens()) {
            int height = Integer.parseInt(tokenizer.nextToken());
            max = Math.max(max, height);
            min = Math.min(min, height);
            sets.put(height, sets.getOrDefault(height, 0) + 1);
        }
    }

    int minTime = Integer.MAX_VALUE;
    int height = 0;

    int inven, time, blocks;
    Loop:
    for (int h = max; h >= min; h--) {                              
        inven = initInven;                                          
        time = 0;                                                   
        for (Map.Entry<Integer, Integer> set : sets.entrySet()) {   
            blocks = Math.abs(set.getKey() - h) * set.getValue();
            if (set.getKey() >= h) {                                
                inven += blocks;                                    
                time += 2 * blocks;                                 
            } else if (blocks <= inven) {                           
                inven -= blocks;                                    
                time += blocks;                                     
            } else continue Loop;                                   
        }

        if (minTime > time) {                                       
            minTime = time;
            height = h;
        }
    }

    result.append(minTime).append(" ").append(height);
}