[Java 자바] 백준 알고리즘 18111번 답 : 마인크래프트

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

18111번: 마인크래프트

 

 

이 문제는 실수할 수 있는 포인트가 굉장히 많다. 

당신의 코드가 어떤 걸 놓쳤는지 같이 알아보자!

 

1. 본 문제는 브루트포스 알고리즘이므로 0~256층까지 모든 경우의 수를 생각해주면 된다.

- 입력받은 블록 층 수에서만 찾으면 안된다.. 필자는 입력받은 블록 수의 min, max값을 구해서 그 사이값만 조사했었는데 블록 층이 300층으로 입력될 수도 있고, min 값이 9층인데 최종 높이가 될 수도 있다.

 

2. 256층까지 계산하는지 확인하길 바란다. 나는 255층까지만 계산해서,, 틀렸었다. 높이는 256까지 가능하다!

테스트 케이스> 출처 : 백준 bamgoesn님 

3 3 1
256 256 256
256 256 256
256 256 256

 

정답 : 0 256

 

3. 시간의 최솟값만 찾다보면 음수도 나오니까,, [시간 >= 0]을 확인하는 조건도 필요하다.

 

[코드]

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

public class Main18111 {
    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[][] world = new int[n][m];
        int minTime = Integer.MAX_VALUE;
        int maxHeight = 0;

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

        int height = 0;
        int cnt = 257;

        while(cnt-->0) {
            int one = 0; // 1번 방법
            int two = 0; // 2번 방법
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    int tmp = world[i][j] - height;
                    if (tmp > 0) // 높이를 줄여야하는 경우 (즉 1번 방법을 써야하는 경우)
                        one += tmp;
                    else if (tmp < 0)
                        two += (-tmp);
                }
            }
            int time = one*2 + two*1;

            if(time >= 0 && (b+one-two) >= 0){ // 인벤터리에 블록이 부족하지 않는 경우
                if(minTime >= time) {
                    minTime = time;
                    if(maxHeight < height)
                        maxHeight = height;
                }
            }
            height++;
        }
        System.out.println(minTime+" "+maxHeight);
    }
}

 

이 문제를 끝으로 백준 Class2 문제를 다 풀었다 ! ㅎㅎ 뿌듯하다. 2월 안에 Class4를 목표로 가보자!