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

728x90

* 문제 이해와 해결 과정

 땅을 고르게 만들어야 함. 땅을 고르게 만드는 방법에는 2가지가 존재하며 각각 소요시간이 다름. 땅의 높이는 0~256이 될 수 있음. 나에게 주어지는 것은 땅의 가로, 세로 길이와 각 땅의 높이, 인벤토리에 보관 중인 블럭들임.

 

첫 시도는 실패했는데, 2가지 작업을 동시에 해줄 수 있다는 점과 높이가 0~256일 때의 모든 경우를 고려하여 탐색해야 한다는 점을 간과했다.

 

결국 문제에서 원하는 것은 최소 시간과 높이다. 높이가 0일 때 시간이 가장 적게 들 수도 있고, 높이가 256일 때 시간이 가장 적게 들 수도 있다. 1)블럭을 파내어 인벤토리에 넣는 작업과 2)인벤토리에 있는 블럭을 꺼내어 쌓는 작업을 적절하게 사용해야한다는 뜻이다. 

 

그래서 높이가 0일때 부터 256일때 까지 모든 경우를 확인하는 방식으로 코드를 작성했다. 

(핵심적인 부분만) 아래의 코드를 요약하자면, 현재 땅의 높이를 하나씩 확인하여 파야할 땅, 쌓아야 할  땅의 갯수를 구한다. 그리고 인벤토리에 존재하는 블럭의 갯수와 땅을 파서 생긴 블럭의 갯수를 더한 값과 높이가 모자르는 땅에 추가해야하는 블럭의 갯수를 비교한다. 전자의 갯수가 후자의 갯수 이상일 경우에만 시간을 계산한다.

 

위의 작업을 높이 0에서 256까지 반복하면 된다.

반응형

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define MIN 0
#define MAX 10000000
using namespace std;
typedef unsigned long long int ll;
int map[501][501];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	int n, m, b, minTime = 99999999, maxHeight = 0;
	cin >> n >> m >> b;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
		}
	}
	
	for (int k = 0; k <= 256; k++)
	{
		int havetodig = 0, havetostack = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (map[i][j] > k)
					havetodig += map[i][j] - k;
				else if (map[i][j] < k)
					havetostack += k - map[i][j];
			}
		}
		if (havetodig + b >= havetostack)
		{
			if (minTime >= havetodig * 2 + havetostack)
			{
				minTime = havetodig * 2 + havetostack;
				maxHeight = k;
			}
		}
	}
	cout << minTime << ' ' << maxHeight;
}