[백준] 마인크래프트

문제

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

분석/설계

답이 여러개인 경우 땅의 높이가 가장 높은 것을 골라야한다는 것을 염두해두어야함.

 

1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.

2. 맵 상에 블록 높이의 최소 값과 최대값을 구합니다.

3. 최소~최대 높이의 수 만큼 반복문을 만듭니다.

   3.1 맵의 크기만큼 반복문을 만들고 맵의 높이 - (최소 값~최대 높이 )를 차이를 구합니다.

   3.2 차이가 0보다 클 경우 시간과 인벤토리에 차이값을 더해줍니다.

   3.3 차이가 0보다 작을 경우 시간과 인벤토리에 차이값을 더하고 빼줍니다.

   3.4 구한 값들을 반복문이 끝날때까지 결과값에 갱신합니다.

4. 결과값을 출력합니다.

 

구현 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
    	// 입력을 Scanner 로 받을 경우 시간 초과
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nmb = br.readLine().split(" ");
        int N = Integer.parseInt(nmb[0]);
        int M = Integer.parseInt(nmb[1]);
        int B = Integer.parseInt(nmb[2]);
		int[][ ]map = new int[N][M];
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<N; i++) { // 변수를 초기화 하면서 최대값, 최소값을 구한다.
            String[] mapRow = br.readLine().split(" ");
			for(int j=0; j<M; j++) {
				int input = Integer.parseInt(mapRow[j]);
				map[i][j] = input;
				max = Math.max(max, input);
				min = Math.min(min, input);
			}
		}
		
		int minTime = Integer.MAX_VALUE; 
		int height = 0; 
		
		for (int i=min; i<=max; i++) { // 최소~최대까지 루프
			int time = 0;
			int inventory = B;
			int diff = 0;
			
			for (int j=0; j<N; j++) {
				for (int k=0; k<M; k++) {
					if (map[j][k] > i) { // 값이 클 경우
						diff = map[j][k]-i; // 차이 값을 구함
						time += diff * 2; // 시간에 (+)
						inventory += diff; // 인벤토리에 (+)
					} else if(map[j][k] < i) { // 값이 작을 경우
						diff = i- map[j][k]; // 차이 값을 구함
						time += diff; // 시간에 (+)
						inventory -= diff; // 인벤토리에 (-)
					}
				}
			}
			
			if(inventory >= 0 && minTime >= time) { // 최소 시간과 높이를 갱신
				minTime = time;
				height = i;
			}
		}
		
		System.out.println(minTime + " " + height);
	}
}

정리

입력받을 시 Scanner를 사용할 경우 백준 채점 사이트에서 시간초과를 만나게됩니다.

Scanner 대신 BufferedReader를 통해 입력을 받아야합니다.

Scanner는 1KB 버퍼 BufferedReader 는 8KB 버퍼로 차이가 있기때문에 입력 값이 많을수록 성능 차이가 있습니다.

참고

https://dlee0129.tistory.com/238

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