[ 백준 ] 18111번 - 마인크래프트

< 문제 정보 >

[ 문제 ]

마인크래프트라는 게임 내에서 집을 짓기 위한 부지를 평평하게 하는 작업을 할 것이다.
부지를 최저 시간과 최고 높이로 하기 위해서는 어떤 높이로 설정해야 하는가를 출력하는 문제

[ 예시 ]

• 입력 :
  3 4 99
  0 0 0 0
  0 0 0 0
  0 0 0 1
  // 3 : 가로 길이, 4 : 세로 길이, 99 : 인벤토리에 있는 블럭의 수
  // 그 이하 칸은 각 블럭의 높이 설정

• 출력 :
  2 0
  // 2 : 걸린 시간, 0 : 땅의 높이

[ 규칙 ]

• 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.
• 걸린 시간이 같을 경우, 높이가 더 높은 값을 출력한다.
• 블럭을 부수는 작업은 시간이 1초 소요되고, 인벤토리에 1개의 블럭이 추가된다.
• 블럭을 쌓는 작업은 시간이 2초 소요되고, 인벤토리에서 1개의 블럭이 사라진다.

[ 백준 ]

• 브루트포스 알고리즘
• 출처 : https://www.acmicpc.net/problem/18111

< 풀이 >

• 입력 받은 블럭의 높이 중 최저 높이와 최고 높이를 받아 반복문을 돌렸다. 예를 들어 블럭들의 높이 중 최저가 40이고 최고 높이가 60이라면 40 ~ 60의 모든 수를 높이로 설정하고, 해당 높이에서 조건이 맞는지 확인하는 식으로 수행하였다.

[ 코드 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BaekJoon18111 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int min=256;
        int max=0;
        int time=0;
        int inven, answertime, answerheight;

        answertime = -1;
        answerheight = -1;
        int[][] field = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<m;j++) {
                field[i][j] = Integer.parseInt(st.nextToken());
                if (min > field[i][j])
                    min = field[i][j];
                else if (max < field[i][j])
                    max = field[i][j];
            }
        }
        inven = b;
        for(int height=min;height<=max;height++) {
            // 최소값 ~ 최대값 사이 값을 높이로 설정하여 모두 계산
            time = 0;   // 각 높이 계산마다 시간 초기화
            inven = b;  // 각 높이 계산마다 인벤토리 초기화
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    if (height <= field[i][j]) {     // 현 블록이 높이보다 높을 경우 = 블럭 빼기
                        time += (field[i][j]-height)*2; // 높이 차이*2만큼 시간 더하기
                        inven += (field[i][j]-height);  // 높이 차이만큼 인벤에 넣기
                    }
                }
            }
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    if (height >= field[i][j]) {     // 현 블럭이 높이보다 낮을 경우 = 블럭 쌓기
                        time += (height-field[i][j]);   // 높이 차이만큼 시간 더하기
                        inven -= (height-field[i][j]);  // 높이 차이만큼 인벤에서 빼기
                    }
                }
            }
            if ((answertime == -1)&&(inven >= 0)) {
                answertime = time;
                answerheight = height;
            }
            if ((answertime >= time)&&(inven >= 0)&&(time>0)) {
                answertime = time;
                if (answerheight < height)
                    answerheight = height;
            }
        }
        System.out.println(answertime + " " + answerheight);
    }
}

해당 문제는 반례 모음을 꼭 보고 하기 바란다.
반례 덕에 최저값(min) 설정이나 걸린 시간이 동일할 경우 더 높은 높이를 출력하기 등에서 많은 문제가 있었고, 아예 전제 자체를 잘못한 경우도 있었다. 
문제를 풀기 위해서 위의 경우를 제외하고 2가지 경우를 더 생각해보았다. 1가지는 최소 시간의 높이가 이미 설치되어 있는 블럭의 높이에서 나온다라는 전제와 전체 블럭의 높이 평균값이 최소 시간의 높이이다라는 2가지를 갖고 문제를 풀었을 때 당연하게도 틀린 전제임을 깨달았다. 
위의 문제는 가능한 모든 경우의 수를 모두 탐색하면서 요구사항에 충족되는 결과만을 가져온다라는 완전 탐색 알고리즘을 이용하였다.