[Java] 백준 18111.마인크래프트

➡️문제 링크

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

 

 

💡아이디어

문제를 읽자마자 든 생각은 이거 어떻게 풀어야 돼? 나 여기서 무너지나..?

이거였고 어차피 못 풀거면 그냥 빨리 답안 보고 이해하는게 빠른거 아닌가 싶었다

근데 뭔가 지는(?) 느낌나서 그래 마지막으로 읽어보자 하면서 다시 읽어보았다.

 

문제를 다시 읽고 요약하자면,

 

(구) 모든 땅의 높이 고르게 하려면 얼마나 걸리고 그 때 가장 높은 높이

즉, 시간의 최솟값과 그 때 높이의 최댓값 을 구하면된다.

그럼 우리는 시간의 최솟값으로 하는 높이의 최댓값을 구하기만 하면 된다!

그럼 높이의 최댓값을 어떻게 구할까?

-> 몰라...

 

왜 모를까?

-> 나의 고질병이기도 한,

항상 문제를 풀때마다 어떠한 특정 알고리즘을 쓴다면 정답을 한 번에 바로 구할 수 있을 거라는 생각때문에 아이디어에 접근하지 못했다.

처음에는 이분탐색을 떠올렸다 주어진 범위를 다시 보니 이분탐색을 쓸 크기가 아닌 것 같았다

그리고 다시 생각해보니 뭔가 0부터 주어진 높이의 최댓값까지 모든 높이를 다 탐색해

최적의 값을 구하는 완탐이 아닐까 싶어 틀리면 어쩔 수 없겠지만

일단 해보자!라는 마음으로 바로 풀어봤다.

 

 

✏️문제 풀이

1.  N*M 탐색- 성공

0부터 주어진 높이 중 최댓값까지 완탐하면서 높이의 최댓값을 구한다.

그 후, N*M으로 저장한 2차원 배열을 순차 탐색하면서 블록 제거 + 블록 삽입을 실행한다.

이때, 우선 기준 높이에 맞춰 기준높이보다 큰 블록들을 제거 한 뒤, 그 다음 다시 for문을 돌려 부족한 곳들을 채우는 걸로 전략을 세웠다.

결과는 성공!

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

/*
 * 인벤토리에 넣기 : 1초
 * 인벤토리에서 꺼내기 : 2초
 * */
public class Main {
	static int N, M, B;
	static int [][] map;
	static int height = 0;
	static int time = Integer.MAX_VALUE;
	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());
		
		// 입력
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		int maxH = 0;
		map = new int[N][M];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				maxH = Math.max(maxH, map[i][j]);
			}
		}
		
		// 구현
		
		for(int i = 0; i <= maxH; i++) {
			solve(i);
		}
		
		// 출력
		System.out.println(time+" "+height);
	}
	
	static void solve(int standard) {
		int store = B;		// 현재 인벤토리 수
		int curTime = 0;
		
		// 1. 블록 제거 ( +2)
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] > standard) {
					curTime += (map[i][j]-standard)*2;
					store += (map[i][j] - standard);
				}
			}
		}
		
		// 2. 블록 삽입 ( +1)
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if (map[i][j] < standard) {
					int count = standard - map[i][j];
					
					if(store >= count) {
						store -= count;
						curTime += count;
					}else return;
				}
			}
		}
		
		if(curTime < time) {
			time = curTime;
			height = standard;
		}else if(curTime == time) {
			if(standard > height) {
				time = curTime;
				height = standard;
			}
		}
	}

}

 

 

2. 각 높이별 count - 성공

1의 방법이 정답이어서 좋았지만 시간복잡도가 너무 크게나왔다

그래서 다른 사람들의 풀이를 보는데 시간복잡도 차이도 나고 다른 방법으로 접근해서 나도 다시 풀어봤다.

나와의 큰 차이점은, 

 

나: N*M 2차원 배열 순차 탐색

다른 풀이: 길이가 257인 1차원 배열 순차 탐색

 

1. 입력 시, 현재 입력받은 값에 해당하는 1차원 배열의 값을 1씩 증가

2. 0부터 256까지 탐색하며 기준 높이에 대해 블록 제거,삽입 진행

 

이 풀이에서 좋았던 점은, 아무래도 높이의 빈도수를 저장했기 때문에

2차원배열을 순차탐색해서 같은 높이가 나와도 각 차례마다 또 계산해야 한 내 풀이와 다르게

해당 높이에 대한 계산을 한 번에 할 수 있었다

아마 이게 아이디어의 차이가 아닐까 싶다!

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

/*
 * 인벤토리에 넣기 : 1초
 * 인벤토리에서 꺼내기 : 2초
 * */
public class Main {
	static int N, M, B;
	static int [] block;
	
	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());
		
		// 입력
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		int minH = Integer.MAX_VALUE;
		int maxH = 0;
		block = new int[267];
		
		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[h]++;
				minH = Math.min(minH, h);
				maxH = Math.max(maxH, h);
			}
		}
		
		// 구현
		int height = 0;
		int resultTime = Integer.MAX_VALUE;
		for(int i = minH; i <= maxH; i++) {
			int curTime = solve(i);
			
			if(curTime < resultTime) {
				resultTime = curTime;
				height = i;
			}else if(curTime == resultTime) {
				if(i > height) {
					resultTime = curTime;
					height = i;
				}
			}
		}
		
		// 출력
		System.out.println(resultTime+" "+height);
	}
	
	static int solve(int standard) {
		int totalTime = 0;		// 총걸리는 시간
		int curStore = B;		// 현재 인벤토리안에 저장된 	블록 수
		
		for(int i = 0; i < 257; i++) {
			int count = block[i];		// 현재 높이에 따른 영역 수
			if(count == 0) continue;	// 해당하는 높이만큼 영역 존재X
			
			if(i < standard) {
				int cnt = count * (standard - i);		// 필요 개수
				
				totalTime += cnt;		// 삽입 1초
				curStore -= cnt;		// 필요한 개수만큼 차감
			}else if( i > standard) {
				int cnt = count *(i - standard);		// 제거해야하는 개수
				
				totalTime += cnt*2;		// 제거 2ch
				curStore += cnt;		// 제거한 수만큼 증가
				
			}
		}
		
		// 판단
		if(curStore < 0) return Integer.MAX_VALUE;	// 해당 높이로 진행X
		else return totalTime;	// 해당 높이로 진행 가능

	}

}

 

 

차이가 확연히 난다!