[18111][java][백준]마인크래프트

알고리즘

• 구현
• 브루트포스 알고리즘

---

문제

---

풀이

주요 문제 풀이는 

1. 땅의 평탄화

2. 최소 시간

이 중요하다

그렇다면 "내가 사용 가능한 블록의 수 = 인벤토리에 있는 블록 수 + 땅에 있는 블록의 수" 이므로

N x M 크기의 집터를 나누어줘서  평탄화 했을 때의 한칸에 쌓을 수 있는 최대 크기를 구한다  ( 사용가능 블록수 / (N * M) )

걸리는 시간을 구하고 0 미만이 되기전까지 (-1값이 나오면 안되므로) 블록의 수를 빼가면서 시간을 구하여 비교하면서 최소 시간을 판별한다.

 

예제 1번을 보자.

N = 3, M = 4, B = 99

0 0 0 0

0 0 0 0

0 0 0 1

 

출력 : 걸리는 시간 : 2 , 땅의 높이 : 0

 

땅의 높이를 모두 같게 만들어야 하므로 내가 사용할 수 있는 블록의 수는 인벤토리에 있는 값과 한칸마다 있는 값들을 더하면 99+0+0+...+1 = 100 이 된다

각 한칸마다 같은 블록의 수를 넣을려면 100 / (3*4) = 8.333 => int 형으로 8 , 모두 한칸에 8층을 넣을 수 있다 ( 8칸이 최대가 된다! 8칸 이상은 평탄화 못함)

그러므로 8칸이 될때 시간을 구하고 min_time변수에 넣어주고, 7칸이 되었을 때의 시간을 구해서 둘이 비교하여 더 작은 시간을 min_time에 넣어준다 그러고 6칸, 5칸, .... 0칸이 될때까지 한다 (-1 음수층이 될 수 없다)

---

java코드

 

 

 

 

 

public class Main{
    public static void main(String[] args) throws IOException {
         // BufferedReader : Scanner 와 유사 (속도 훨씬 빠름)
        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[][] map = new int[n][m];
        int total = b;
        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());
                total += map[i][j];
            }
        }
        // 한칸에 가질 수 있는 최대높이
        int height = (total) / (n * m);
        //System.out.println(height);
        if (height > 256) height = 256;
        int min_time = Integer.MAX_VALUE;
        // System.out.println(time); 2147483647
        int final_Height = height;
 
        while (height >= 0) {
            int currentTime = 0;
            // 현재 높이에서의 시간 구하기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] <= height)
                        currentTime += (height - map[i][j]);
                    else
                        currentTime += (2 * (map[i][j] - height));
                }
            }
            if (currentTime < min_time) {
                min_time = currentTime;
                final_Height = height;
            }
            height--;
 
        }
        System.out.println(min_time + " " + final_Height);
    }
}