[알고리즘/문제풀이/BOJ 18111번]마인크래프트

마인크래프트 문제는 지형을 평탄화할 수 있는 모든 경우를 고려하여 계산하는 문제이다. 평탄화된 지형의 최소 높이는 0, 최대 높이는 지면의 블록 개수와 인벤토리에 있는 블록 개수를 면적으로 나눈 값이다. 이 두 값 사이의 값을 높이로 가지기 위해 블록을 부수거나 쌓아야 하는 데 이때 가장 시간이 적게 걸리는 높이를 찾으면 된다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>

int N, M, B;
int land[520][520];
int sum = 0;
int time;
int min=987654321;
int height;

int main(void) {
	scanf("%d %d %d", &N, &M, &B);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &land[i][j]);
			sum += land[i][j];
		}
	}

	sum += B;

	for (int i = 0; i <= sum / (N * M); i++) {
		time = 0;
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (land[j][k] > i) {
					time = time + 2*(land[j][k]-i);
				}
				if (land[j][k] < i) {
					time = time + (i - land[j][k]);
				}
			}
		}
		if (min >= time) {
			min = time;
			height = i;
		}
	}

	printf("%d %d\n", min, height);
}

문제의 지문은 다음과 같습니다.

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