[백준 18111] 마인크래프트 (JAVA)

백준 18111번 문제 - 마인크래프트

18111번: 마인크래프트

---

문제 분석

 

 

 

• 입력받은 땅을 똑같은 높이로 만들어야 한다.
  • 땅의 크기 (N*M)
• 땅을 다듬는 방법과 시간소요는 다음과 같다.
  • 1초 : 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
  • 2초 : 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
• 인벤토리에 담겨진 블록은 B개이다.
• 이때 땅을 고르게 만드는데 가장 짥은 소요 시간과 그 당시 땅의 높이 출력
  
  • 답이 여러개일 경우, 가장 높은 높이를 출력

---

 

해결 키 포인트

 

• 방법 1 : 는 땅의 높이의 평균을 구해 평균과 평균+1로 땅을 다듬을 때 시간 중 작은 시간으로 처리
  • 실패 ! 1퍼센트도 되지 못했다.
• 방법 2 : 가장 작은 땅 크기 부터 큰 땅 크기까지 모든 소요 시간을 구해 가장 작은 시간으로 처리 
  • 성공 ! 시간초과를 고려서 1번 방법을 선택하였지만, 시간은 넉넉했다.
• 인벤토리가 모자랄 경우 처리 : 인벤토리에 넣고 빼는 작업을 일단 반복 후, 마지막에 0보다 인벤토리 속 블록 수가 작은지 확인
• 초기 시간 값은  99999999로 ! (가장 큰 수)
• 두 높이의 소요 시간이 동일 할 경우, 높이가 큰 것으로 한다 !

---

 

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[][] nums = new int[N][M];
        int min = 0, max = 257;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
                min = Math.min(min, nums[i][j]);
                max = Math.max(max, nums[i][j]);
            }
        }

        int resultFloor = 0;
        int resultTime = 99999999;
        for (int floor = min; floor <= max; floor++) {
            int b = B;
            int newTime = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (floor > nums[i][j]) {
                        b -= floor - nums[i][j];
                        newTime += floor - nums[i][j];
                    } else if (floor < nums[i][j]) {
                        b += nums[i][j] - floor;
                        newTime += ((nums[i][j] - floor) * 2);
                    }
                }
            }
            if(b < 0) {
                break;
            }
            if(newTime <= resultTime) {
                resultTime = newTime;
                resultFloor = floor;
            }
        }

        System.out.println(resultTime + " " + resultFloor);
    }
}