백준 18111 마인크래프트 (c++) : 피너클

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

18111번: 마인크래프트

단순히 구현하는 문제다.

int n, m, b;
int map[501][501];
bool visited[501][501];
int block = 0;

visited는 방문 완료한 땅, block은 사용할수있는 블럭의 총 수량이다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> map[i][j];
		block += map[i][j];
	}
}
block += b;

입력받으며 block을 추가해주고 마지막에는 b도 block에 더해준다.

int ans = 987654321, l = 0;

for (int i = 256; i >= 0; i--) {
	int _new = solve(i);
	if (ans > _new) {
		ans = _new;
		l = i;
	}
}

ans는 시간, l은 높이다.

solve함수를 돌린뒤 만약 ans가 solve보다 높다면 값을 교체해준다.

int solve(int end) {
	if (block < end) return 987654321;

	memset(visited, false, sizeof(visited));

solve함수는 블럭을 쌓을 높이를 전달받는다.

만약 사용할수 있는 모든 블럭의 수가 end보다 작다면 매우 높은 시간을 리턴한다. 여기서는 987654321을 리턴했다.

명령문 시작전 visited를 초기화해준다.

int can = b, time = 0;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (map[i][j] > end) {
			visited[i][j] = true;
			can += map[i][j] - end;
			time += 2 * (map[i][j] - end);
		}
	}
}

can은 사용할수 있는 블럭의 수, time은 현재까지 사용한 시간이다.

모든 블럭을 보며 만약 현재 위치의 블럭이 최종 높이보다 높다면

visited를 체크해주고, can에 (블럭을 제거한 수)를 더해준뒤 time에는 2 * (블럭을 제거한 수) 을 더해준다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (!visited[i][j] && map[i][j] < end) {
			time += end - map[i][j];
			if (can - end + map[i][j] < 0) return 987654321;
			can -= end - map[i][j];
		}
	}
}
return time;

그후 다시 모든 블럭을 돌아보며

방문하지 않았고 블럭의 개수가 end보다 낮은 위치가 있다면

time에 블럭을 쌓은 수를 더해주고

can에 블럭을 쌓는데 걸린 시간을 더해준다.

만약 can이 0보다 낮아진다면 987654321를 리턴해준다.

모든 반복문을 돌린 뒤 time을 리턴해준다.

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <string.h>

using namespace std;

int n, m, b;
int map[501][501];
bool visited[501][501];
int block = 0;

int solve(int end) {
	if (block < end) return 987654321;

	memset(visited, false, sizeof(visited));
	int can = b, time = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] > end) {
				visited[i][j] = true;
				can += map[i][j] - end;
				time += 2 * (map[i][j] - end);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j] && map[i][j] < end) {
				time += end - map[i][j];
				if (can - end + map[i][j] < 0) return 987654321;
				can -= end - map[i][j];
			}
		}
	}
	return time;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> b;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			block += map[i][j];
		}
	}
	block += b;

	int ans = 987654321, l = 0;

	for (int i = 256; i >= 0; i--) {
		int _new = solve(i);
		if (ans > _new) {
			ans = _new;
			l = i;
		}
	}

	cout << ans << ' ' << l << endl;
}

전체코드다.