[백준/C++] 18111번: 마인크래프트

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

18111번: 마인크래프트

• 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include<cmath>
#define LL long long
using namespace std;
LL arr[500][500];
int main() {
	int n = 0;
	int m = 0;
	LL b = 0;
	cin >> n >> m >> b;
	LL Min = 64000001;
	LL Max = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] < Min) Min = arr[i][j];
			if (arr[i][j] > Max) Max = arr[i][j];
		}
	}

	LL time = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			time += (arr[i][j] - Min) * 2;
			b += arr[i][j] - Min;
		}
	}
	LL Mintime = time;
	LL ground = Min;
	for (int i = 0; i < 256; i++) {
		if ((Min + 1) == 257 || (Min + 1) > Max) break;
		else {
			Min++;
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (arr[j][k] >= Min) {
						time -= 2;
						b--;
					}
					else if (arr[j][k] < Min) {
						time++;
						b--;
					}
					
				}
			}
			if (b < 0) {
				break;
			}
			if (Mintime >= time) {
				Mintime = time;
				ground = Min;
			}
		}
	}

	cout << Mintime << " " << ground;


	return 0;
}
}

• 알고리즘 분류 : 구현
• 문제 해설

시간초과되지 않는 방법을 찾아내는게 관건인 문제였다. 

나의 접근 방법은 최대로 쌓을 수 있는 블럭이 256개이므로 최소 블럭 개수로 땅을 고른다음 최대 개수까지 쌓아가는 방식으로 했다. 그렇게 하면 256*500*500이므로 1억번 연산을 넘어가지 않았다.

주의해야했던 점은 블럭(Min)을 늘려가면서 초기 블럭이 현재 블럭보다 많았는지 적은 상태인지에 따라 시간을 다르게 바꿔야 한다는 점이다. 블럭을 없애는데에는 2초가 걸리고 블럭을 쌓는데에는 1초가 걸리므로 현재 블럭이 초기 블럭보다 크다면 time에 1을 더해야하고 현재 블럭이 초기블럭보다 작다면 오히려 블럭을 다시 복귀시키는 것이므로 2초를 더해야한다. 

또 다른 주의했던 점은 인벤토리였다. 인벤토리에 뻈던 블럭만큼 더해야하는 건 물론이고 블럭을 쌓았다면 인벤토리에서 빼야하는데 이때 모든 땅을 다 돌고나서 인벤토리에 블럭이 적자가 났다면 방금 돌았던 것은 무효가 되고 그 전에 갱신했던 시간과 땅의 높이가 정답이 된다.

256이상의 땅의 높이까지 가거나 최대높이보다 더 큰 값까지 가면 종료시켜주는 것도 필요하다. 최대높이보다 큰 값까지 갔을 때 종료하는 건 굳이 정답에 영향은 안줄 것 같지만 최대 높이 이상은 어차피 최소 시간이 될 수 없으므로 조금이라도 빨리 종료시키기 위해 써줬다.