[백준] 18111번 마인크래프트 (완전탐색_JAVA)

문제를 꼼꼼 읽어야 한다!

조건 하나 놓쳐서 30분,

경계 놓쳐서 30분..

 

문제 자체는 어렵지 않지만,

이런 조건을 못보는 순간

문제 푸는 시간이 2배 이상 걸리는 거 같다.

앞으로는 천천히 읽자!

 

 

---

문제

 

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

18111번: 마인크래프트

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 완전탐색

모두 동일한 높이로 바꿔야 하는 문제다.

가장 낮은 높이부터 높은 높이까지 반복문을 돌며, 시간을 체크하면 된다.

여기서 조심해야 할 점은, 작업 시간이 동일하다면 높이가 가장 높은 경우를  출력해야 한다.

 

또한, 시간초과 때문에 이런방법 저런방법 다 써봤는데 그냥 Scanner가 문제였다.

만약 시간초과가 발생했는데 예제와 반례 모두 맞다면 BufferedReader로 바꿔보자.

 

풀이 과정

1.

높이 h, 너비 w, 블럭 b를 입력받는다.

가장 높은 높이와 낮은 높이를 알기 위해 min과 max를 초기화 해준다.

 

2.

2차원 배열을 생성하고, 각각 높이를 입력받는다.

여기서 min과 max를 비교하며, 조건에 맞다면 값을 변경한다.

 

3.

min부터 max까지 반복문을 돌며, 현재 높이로 바꿀 때의 시간을 구한다.

현재 좌표의 높이가 기준보다 낮다면, 인벤토리에서 필요한 만큼 빼고 시간을 필요한 높이만큼 더한다.

현재 좌표의 높이가 기준보다 높다면, 필요한 만큼의 높이*2를 시간에 더해준다.

 

4.

만약 기준 높이에 대한 2차원 배열의 반복문이 종료되었을 때, 인벤토리가 0보다 적다면, 반복문을 종료해준다.

더 높은 높이로 비교해봐도 인벤토리의 블럭이 적어서 불가능 하기 때문이다.

 

5.

시간이 현재 가장 적은 시간보다 적고, 높이가 높거나 같다면 값을 변경하고 출력한다.

 

 

---

코드

 

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

public class Test_18111_마인크래프트 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		//땅의 높이 입력받고, 최소값 최대값 구하기
		int[][] map = new int[h][w];
		for(int i=0; i<h; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<w; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if(max<map[i][j]) max = map[i][j];
				if(map[i][j]<min) min = map[i][j];
			}
		}
		
		int answer = 0;
		int answerTime = Integer.MAX_VALUE;
		
		//완전탐색 min부터 max까지
		for(int c=min; c<=max; c++) {
			
			int time = 0;
			int bag = b;

			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
				
					//현재 좌표의 높이가 c보다 낮으며, 인벤토리에 블록이 있을 때
					if(map[i][j]<c) {
						bag-=(c-map[i][j]);
						time+=(c-map[i][j]);
					}
					
					//현재 좌표의 높이가 c보다 높을 때
					else if(c<=map[i][j]) {
						bag+=(map[i][j]-c);
						time+=(2*(map[i][j]-c));
					}	
				}
			}
			
			if(bag<0) break;
			
			if(time<=answerTime && answer<=c) {
				answer = c;
				answerTime = time;
			}
		}
		
		//출력
		System.out.println(answerTime +" "+ answer);
		
	}
}

 

 

(❁´◡`❁)

끝!