[백준] 알고리즘 분류(브루트 포스,JAVA)18111번, 마인크래프트

문제 링크

18111번: 마인크래프트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 땅 고르기 작업은 모든 배열의 값이 동일한 값이 되어야 합니다.

2. 땅을 파는 작업은 2초, 인벤토리에 땅을 채우는 작업은 1초 걸립니다.

3. 땅 고르기가 완료되는 최소 시간과 높이를 결과로 출력합니다.

4. 최소 시간이 여러 개 존재하면 높이는 가장 큰 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 블록의 높이가 될 수 있는 모든 경우를 탐색합니다.

 

3. 최소 시간과 높이를 결과로 출력합니다.

 

블록의 높이가 될 수 있는 경우.

 

블록의 최대 높이 ≥ 될 수 있는 높이 ≥ 블록의 최소 높이

 

땅을 파는 작업이 2초가 걸리기 때문에 블록을 놓는 작업을 많이 하는 것이 더 효율적입니다.최소 높이에서 더 파는 것보다 최대 높이를 파서 최소 높이를 올리는 것이 좋습니다.

 

높이를 만들 수 있는지 탐색.

 

아래와 같은 블록에서 높이 3으로 만들 때(B : 0일 때)

4(-1)	2(+1)
2(+1)	2(+1)

땅을 파는 것은 B : +

땅을 놓는 것은 B : -

B : B + 1 - 1 -1 -1 = -2

B가 음수이면 인벤토리에 있는 땅보다 더 많이 사용한 것으로 해당 높이를 만들 수 없습니다.

B가 양수이면 인벤토리에 있는 땅보다 적게 사용한 것으로 해당 높이를 만들 수 있습니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N : 3

M : 4

B : 0

64	64	64	64
64	64	64	64
64	64	64	63

 

2. 블록의 높이가 될 수 있는 모든 경우를 탐색합니다.

 

높이가 될 수 있는 경우

64 ≤ 높이 ≤ 63

 

높이가 64일 때

64	64	64	64
64	64	64	64
64	64	64	64(+1)

B : 0 + (-1) = -1

B가 음수이기 때문에 만들 수 없습니다.

 

높이가 63일 때

63(-1)	63(-1)	63(-1)	63(-1)
63(-1)	63(-1)	63(-1)	63(-1)
63(-1)	63(-1)	63(-1)	63

B : 0 + 1 + .... + 1 = 11

B가 양수이기 때문에 만들 수 있습니다.

걸린 시간 : 2초 × 11 = 22

높이 : 63

 

3. 최소 시간과 높이를 결과로 출력합니다.

 

22 63

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 블록의 정보를 띄어쓰기 기준으로 나누었습니다.
• 높이가 가능한 모든 경우를 blockCheck함수를 시간과 높이를 구합니다.
• 최단 시간과 높이를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• blockCheck함수는 땅 고르기할 때 높이를 만들 수 있는지 확인 및 시간을 구합니다.

 

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


public class Main {
    static int N,M,B, max = 0, min = 256, answer = Integer.MAX_VALUE, height;
    static int[][] block;	//블록 정보 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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];
        //블록 내용 및 최대 높이, 최소 높이 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++){
                int h = Integer.parseInt(st.nextToken());
                block[i][j] = h;
                min = Math.min(h, min);
                max = Math.max(h, max);
            }
        }
        //높이 모든 경우 탐색
        for(int i=max;i>=min;i--)
            blockCheck(i);
        bw.write(answer + " " + height);	//최소 시간 및 높이 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //해당 높이 만들 수 있는지 확인 및 시간 구하는 함수
    static void blockCheck(int h){
        int time = 0;
        int b = B;
        //각 블록 높이 변경하기.
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(time > answer)	//최소 시간보다 커질 경우 종료.
                    return;
                if(block[i][j] > h){	//땅 파기.
                    int sub = block[i][j] - h;
                    time += 2 * sub;
                    b += sub;
                }else if(block[i][j] < h){	//땅 놓기
                    int sub = h - block[i][j];
                    time += sub;
                    b -= sub;
                }
            }
        }
        //최소 시간 비교하기.
        if(b >= 0 && answer > time){
            answer = time;
            height = h;
        }
    }
}