#18111 : 마인크래프트

풀이방법

사용된 것:

브루트포스 알고리즘

 

2022.06.17

문제에 나와있는 것을 그대로 해보면 풀리는 문제이다. 수의 범위가 적기 때문에 브루트포스 식으로 일일이 세어서 풀어도 시간초과 없이 해결된다.

 

나는 다음과 같이 구현하였다.

 

먼저, 현재 존재하는 땅 중 가장 낮은 땅보다 더 파내려가면 무조건 손해이며, 가장 높은 땅보다 더 쌓는 것도 무조건 손해이다. 그러므로 정답은 반드시 본래 존재하는 땅의 높이 중 최솟값과 최댓값 사이에 존재한다.

 

본래 땅 높이의 최솟값부터 최댓값까지에 대하여,

모든 땅을 해당 높이로 평평하게 맞추려면 블럭과 시간이 얼마나 필요한지 직접 세었다.

그 다음, 주머니에 있는 블럭이 모자라지 않았다고 판별될 때만, (걸린 시간, 높이)를 짝지어 TreeMap에 넣었다. Key값을 시간으로, Value를 높이로 하였다.

 

이렇게 한 뒤 TreeMap의 가장 앞에 있는 엔트리의 Key와 Value를 순서대로 공백을 사이에 두고 화면에 출력하면 된다.

 

코드

Java(2022.06.17)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		long b = Long.parseLong(st.nextToken());
		
		int[] arr = new int[n*m];
		
		for(int i=0; i<n*m; i=i) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) arr[i++] = Integer.parseInt(st.nextToken());
		}
		
		//현재 존재하는 땅 중 가장 낮은 것과 높은 것의 높이 구하기
		Arrays.sort(arr);
		int min = arr[0];
		int max = arr[(n*m)-1];
		
		//각 높이마다 그 높이를 만들기 위해 필요한 시간 및 블럭 세기
		TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
		for(int i= min; i<=max; i++) {
			//모든 땅의 높이를 i로 맞출 때...
			long sum = 0;	//필요한 시간
			long usedblocks = 0;	//사용되는 블럭
			for(int j: arr) {
				if(j>i) {sum += 2*(j-i); usedblocks -= j-i;}	//i보다 높아서 깎아야 하는 땅
				else {sum += i-j; usedblocks += i-j;}	//i보다 높지 않은 땅
			}
			if(usedblocks<=b) tm.put(sum, i);	//주머니에 있는 블럭이 모자라지 않았다면 TreeMap에 넣기
		}
		
		//정답 출력
		System.out.print(tm.firstKey() + " " + tm.firstEntry().getValue());
	}

}