백준 18111번 : 마인크래프트 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

마인크래프트 실버 2

 

📖 문제

 

완전탐색 문제로 땅 고르기를 하면된다.

 

주어진 땅 높이들의 최소, 최댓값을 구한 후

최소~최대 높이까지 탐색을 해서 최단 시간이면서 가장 높은 높이를 구하면된다. 

 

 

나는 잘못 푼게 있는데 

맵 탐색중 2번 작업시 인벤토리내에 블록이 없으면 바로 불가능하다고 판단하고 멈췄는데

 

생각이 짧았다..

현재 위치에서 인벤토리가 비어있더라도

다른 위치에서 1번 작업을 통해 블록을 인벤에 저장하고 현재 위치에서 사용할 수 있는데

이걸 생각못한게 정말 .. 눈물이난다.

 

 

---

🔅 문제 풀이

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

public class Main {
    static int totalTime = Integer.MAX_VALUE;
    static int height = 0;

    static int[][] map;
    static int n;
    static int m;

    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());
        int b = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        int min = Integer.MAX_VALUE;
        int max = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                // 최대 최소값 획득
                min = Math.min(min, map[i][j]);
                max = Math.max(max, map[i][j]);
            }
        }

        // min ~ max까지 다 해보기
        for (int targetHeight = min; targetHeight <= max; targetHeight++) {
            landLeveling(targetHeight, b);
        }

        System.out.println(totalTime + " " + height);


    }

    // 1. 가장 위 블록 제거후 인벤토린 넣기 : 2초
    // 2. 인벤토리에서 블록 하나 꺼내서 블록위에 쌓기 : 1초
    // 최소시간 구하기 , 같은게 많다면 높이가 가장 높은 걸로
    private static void landLeveling(int targetHeight, int inventory) {
        int currentTime = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == targetHeight) continue;

                // 목표 블록 높이보다 높다면 1번 작업 실행
                if (map[i][j] > targetHeight) {
                    currentTime += (map[i][j] - targetHeight) * 2;
                    inventory += map[i][j] - targetHeight;
                    continue;
                }

                // 목표 블록 높이보다 낮다면 2번 작업 실행
                if (map[i][j] < targetHeight) {
                    int secondWork = targetHeight - map[i][j]; // 2번 작업 결과

                    // 작업 시간 추가
                    currentTime += secondWork;
                    // 2번 작업으로 인한 인벤토리 블록 꺼내기
                    inventory -= secondWork;
                }
            }
        }

        // 땅고르기 후 결과를 봤을때 인벤토리가 음수라면 불가능한 높이이므로 return
        if (inventory < 0) return;

        // 최소시간이면 갱신
        if (currentTime < totalTime || (currentTime == totalTime && targetHeight > height)) {
            totalTime = currentTime;
            height = targetHeight;
        }


    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.