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

문제

[C++] 백준 18111: 마인크래프트 SILVER 2
https://www.acmicpc.net/problem/18111

 

---

 

접근 방법

이 문제는 땅의 모든 칸을 같은 높이 i로 평탄화할 때 걸리는 최소 시간과 그때의 높이를 구하는 문제다.

 

핵심 아이디어는 다음과 같다.

• 목표 높이 i는 0 ~ 256 전부 후보다.
  현재 맵에 “i 높이 칸이 0개”라도 그 높이로 평탄화하는 게 최적일 수 있다.
• 각 후보 높이 i에 대해,
  • 높이가 더 높은 칸(j > i)은 블록을 제거해야 하고 (1개당 2초)
  • 높이가 더 낮은 칸(j < i)은 블록을 설치해야 한다 (1개당 1초)
• 제거하면 블록이 인벤토리에 들어오므로, 최종적으로 인벤토리 블록이 음수가 되면 그 높이는 불가능하다.
  (인벤토리 블록이 음수라는 것은, 갖고 있는 블록보다 오바해서 사용한 것이다.)
• 가능한 높이들 중에서 시간이 최소인 것을 고르고, 시간이 같다면 문제 조건대로 높이가 더 높은 것을 선택한다.

이 문제는 브루트포스처럼 보이지만, 높이가 0~256로 고정되어 있어서 257 * 257 정도만 계산하면 되기 때문에 충분히 빠르게 해결 가능하다.

 

상세 아이디어

1. 높이별 개수로 압축하기

• 입력으로 들어오는 모든 칸의 높이를 그대로 저장하지 않고, vect[h] = 높이가 h인 칸의 개수로 세어둔다.
• 이렇게 해두면, 나중에 후보 높이 i를 검사할 때 각 높이 j에 대해 “몇 칸이 있는지”만 보면 되어서 계산이 단순해진다.

vector<int> vect(257, 0);
for (int y = 0; y < n; y++)
{
	for (int x = 0; x < m; x++)
	{
		int num = 0;
		cin >> num;
		vect[num]++;
	}
}

 

2. 목표 높이 i를 하나씩 전부 검사 (0~256)

• 각 후보 높이 i에 대해 필요한 시간 t, 남는 블록 수 block을 계산한다.
  • 시작 인벤토리: block = b
  • 시간 초기화: t = 0
• 그리고 모든 높이 j에 대해:
  • j > i : 제거해야 함
    • 높이 차이는 j - i
      해당 높이 칸이 vect[j]개 있으니 제거 블록 수는 vect[j] * (j - i)
      • 시간: 제거 1개당 2초 → *2
      • 인벤토리: 제거한 만큼 블록이 늘어남
  • j < i : 설치해야 함
    • 높이 차이는 i - j
      설치 블록 수는 vect[j] * (i - j)
      • 시간: 설치 1개당 1초
      • 인벤토리: 설치한 만큼 블록이 줄어듦

 

3. 인벤토리가 음수면 불가능

• 어떤 후보 높이 i는 블록이 부족해서 만들 수 없다.

 

4. 최소 시간 갱신 + 동률이면 더 높은 높이 선택

• 문제 조건이 “시간이 같으면 높이가 더 큰 것”이므로,
  i를 0부터 증가시키면서 검사할 때 t <= time으로 갱신하면 자동으로 조건을 만족한다.

 

 

구현 시 주의할 점

• 목표 높이 i를 “존재하는 높이만” 보면 틀림.
  vect[i] == 0인 높이도 최적이 될 수 있다.
  • 예를 들어 0과 2만 있어도 최적 높이는 1일 수 있음.
    그래서 i=0~256 전부를 후보로 봐야 한다.
• 블록 계산에 “높이 차이”를 반드시 곱해야 함.
  반드시 (j-i) 또는 (i-j)를 곱해 “블록 개수”를 계산해야 한다.
• 시간/블록은 long long으로 처리하는 게 안전
  곱셈이 여러 번 들어가서 int로도 되는 경우가 많지만, 안전하게 long long으로 두는 게 좋다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

	int n = 0, m = 0, b = 0;
	cin >> n >> m >> b;

	vector<int> vect(257, 0);
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			int num = 0;
			cin >> num;
			vect[num]++;
		}
	}
	long long time = 21e8, height = 0;
	for (int i = 0; i < 257; i++)
	{
		long long t = 0, block = b;
		for (int j = 0; j < 257; j++)
		{
			if (vect[j] == 0 || i == j) continue;

			if (i < j)
			{
				t += ((vect[j] * (j - i)) * 2);
				block += ((vect[j] * (j - i)));
			}
			else
			{
				t += (vect[j] * (i - j));
				block -= ((vect[j] * (i - j)));
			}
		}
		if (block < 0) continue;
		if (t <= time)
		{
			time = t;
			height = i;
		}
	}
	cout << time << ' ' << height;

	return 0;
}