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

Minsu Lee·2023년 3월 3일

Java algorithm

baekjoon

목록 보기

11/16

🎆백준 18111번 마인크래프트🎆

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/18111

🔍예제 입력

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

🔍예제 출력

2 0

📌풀이

🔍풀이 설명

Bruteforcing 방식으로 풀이하는 문제이다.

Brute-Force : 완전탐색 알고리즘으로 볼 수 있다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

우선 입력 받은 땅의 높이 중에 최소값과 최대값을 구하고 최솟값부터 최대값까지 전부 땅을 고르게 해본 다음 인벤토리가 충족하고, 시간이 최소로 걸리는 값을 구한다. 이때 시간은 비교하고 있는 최소 시간보다 작거나 같은 경우에 값을 업데이트한다.

package Implementation;

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

//마인크래프트
public class p18111 {
    static int N, M, B;
    static int block[][];

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

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

        int answerHeight = -1;
        int answerTime = Integer.MAX_VALUE;

        //최소 층에서 최대 층까지 모든 경우 비교
        for(int i=min; i<=max; i++){
            int time = 0;
            int inventory = B;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    int diff = block[j][k] - i;
                    if(diff > 0){ //제거하고 인벤토리에 넣어야함
                        inventory += Math.abs(diff);
                        time += (Math.abs(diff)*2);
                    }
                    else if (diff < 0){ //인벤토리에서 꺼내야함
                        inventory -= Math.abs(diff);
                        time += Math.abs(diff);
                    }
                }
            }
            if(inventory >= 0){ // 인벤토리 안에 값이 남거나 0일 경우만 통과
                if(time <= answerTime){ //시간은 같거나 작은 거로 해야함 (높이가 최대인 것을 구해야하기 때문)
                    answerTime = time;
                    answerHeight = i;
                }
            }
        }

        System.out.print(answerTime + " "+ answerHeight);
    }
}