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

문제 링크

---

18111번: 마인크래프트

접근 방법

---

1. 어떤 알고리즘을 적용시켜야 할지 모르겠다면 우선 브루트 포스로 구현합니다.
2. 무엇을 기준으로 반복문을 돌려야 시간을 줄일 수 있을지 생각해 봅니다.

소스 코드

---

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<vector<int>> land;
	int maxHeigt = 0, minTime = 128000000, Time, n, m, b, tmp, cur, start = 256, end = 0;
	
	cin >> n >> m >> b;

	land.resize(n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> tmp;
            
			if (tmp > end)
				end = tmp;
                
			if (tmp < start)
				start = tmp;
                
			land[i].emplace_back(tmp);
		}
	}
    
	cur = start; // cur은 땅 고르기를 할 기준 높이입니다.
	while (cur <= end) // 땅 고르기 작업을 start부터 end까지 해봅니다.
	{
    
		tmp = b; // tmp에는 현재 인벤토리에 들어있는 블록 수를 넣어줍니다.
		Time = 0;
        
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < m; k++)
			{
				if (land[j][k] > cur) // 기준 높이보다 크다면 땅을 파줍니다.
				{
					Time += (land[j][k] - cur) << 1; // 제거한 블록 수의 2배가 걸린 시간입니다.
					tmp += (land[j][k] - cur); // 판 블록은 다시 사용할 수 있으므로 넣어줍니다.
				}

				else if (land[j][k] < cur) // 기준 높이보다 낮다면 블록을 쌓아줍니다.
				{
					Time += cur - land[j][k];
					tmp -= (cur - land[j][k]); // 사용한 블록만큼 빼줍니다.
				}
			}
		}
        
		if (tmp >= 0) // 남은 블록 수가 음수이면 cur 높이로 땅고르기를 못한다는 뜻이므로 무시합니다.
		{
			if (minTime > Time) 최소시간보다 현재 걸린 시간이 더 적을 때
			{
				maxHeigt = cur;
				minTime = Time;
			}

			else if (minTime == Time) // 최소시간과 걸린시간이 같은데 현재높이가 더 높을 때
				if (cur > maxHeigt)
					maxHeigt = cur;
		}
		cur++;
	}
	cout << minTime << ' ' << maxHeigt;

	return 0;
}

코드 설명

---

변수

maxHeight는 출력해야 할 높이, minTime은 출력해야 할 시간입니다.

cur은 지금 평탄화할 땅의 높이, Time은 cur로 땅 고르기를 했을 때 걸린 시간입니다.

land는 땅의 높이를 저장하는 이차원 벡터입니다.

 

코드

먼저 땅의 높이를 입력받으면서 가장 낮은 땅의 높이와 가장 높은 땅의 높이를 찾습니다. 

cur을 start부터 end까지 1씩 증가시키면서 cur 높이로 땅 고르기 작업을 진행합니다.

cur보다 땅의 높이가 낮으면 블록을 쌓고, 높이가 높으면 땅을 파고 인벤토리에 블록을 넣습니다.

해당 작업을 했을 때 인벤토리에 들어있는 블록의 수가 음수이면, 해당 작업을 못한다는 뜻이므로 시간을 비교할 필요가 없습니다.

인벤토리에 들어있는 블록 수가 0 이상일 때, 작업이 최소시간보다 적게 걸렸는지 확인합니다. 

만약 걸린 시간이 최소시간과 같을 경우 최대높이를 비교합니다. 

 

개선

n * m의 땅의 정보로 이차원 배열을 만드는 것보다 0 ~ 256의 땅의 높이의 기수정렬로 접근하는 방법이 훨씬 빠릅니다.

n * m으로 반복문을 돌렸을 때 최악은 250000번이지만 높이로 돌렸을 경우 257입니다.

백준에 예제 입력 1을 예로 들면 n * m으로 반복문을 돌리면 12번씩 돌려야 하지만, 높이로 접근하게 되면 0과 1 밖에 없으니 반복문을 2번만 돌리면 됩니다.

또한 코드 17번째 줄에서 입력받을 때 이중 for문을 사용하는데 for문 한 번으로 바꿉니다.

start와 end를 17번째 줄 for문에서 구하는데 n*m번 비교하는것 보다 더 나은 방법으로 바꿔줍니다.

46번째 줄과 52번째 줄에서 Time을 n*m번 연산하는데 사용한 블록과 파낸 블록만 세서 Time을 구하는 방법으로 접근합니다.

인벤토리에 남은 블록 수가 음수가 되는 시점에서 그 후의 높이로 땅 고르기를 못하므로 반복문을 종료시킵니다.

개선된 코드

---

#include <iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int maxHeigt = 0, minTime = 128000000, Time, n, m, b, tmp, start = 256, end = 0;
	int used, earned, cur = 0, height, land[257] = { 0 };
	
	cin >> n >> m >> b;

	n *= m;

	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		if (tmp > end)
			end = tmp;
		if (tmp < start)
			start = tmp;
		land[tmp]++;
	}

	height = start;

	while (height <= end)
	{
		used = earned = 0;
		cur = start;

		while (cur != height)
		{
			used += (height - cur) * land[cur];
			++cur;
		}
		
		while (++cur <= end)
			earned += (cur - height) * land[cur];

		if (earned + b < used)
			break;
		Time = (earned << 1) + used;
        
		if (minTime >= Time)
		{
			maxHeigt = height;
			minTime = Time;
		}
		++height;
	}
	cout << minTime << ' ' << maxHeigt;

	return 0;
}

 

 

처음 작성한 코드와 개선된 코드의 결과입니다.

실행 시간 차이가 많이 나는 것을 확인할 수 있습니다.