[백준] 18111번 - 마인크래프트 (C++)

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

 

 

풀이과정

해당 문제에서 신경써야했던 부분은 이와 같다.

1. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

2. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

3. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

 

문제에서는 땅 고르기를 하면서 걸리는 최소시간과 그 땅의 높이를 구해야한다고했다.

땅의 높이의 범위가 0 ~ 256 까지로 적은 범위 내에 제한이 되어있으니 모든 땅 높이를 반복문을 돌며, targetHeight를 기준의 높이로 모든 땅을 만들어보고 블럭개수내에 가능한지, 시간이 가장 적은지를 확인하며 결과값을 구하였다.

 

code

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {

	int n, m, b, land;

	cin >> n >> m >> b;

	unordered_map<int, int> frequency;
	for (int i = 0; i < n * m; i++) {
		cin >> land;
		frequency[land]++;
	}

	int inventory, time;
	int minTime = INT_MAX, bestHigh = 0;
	for (int targetHeight = 0; targetHeight <= 256; targetHeight++) {
		time = 0;
		inventory = b;

		for(const auto& [height, freq] : frequency) {
			if (height < targetHeight) {
				int blocksNeeded = (targetHeight - height) * freq;
				inventory -= blocksNeeded;
				time += blocksNeeded;
			} else if (height > targetHeight) {
				int blocksRemoved = (height - targetHeight) * freq;
				inventory += blocksRemoved;
				time += blocksRemoved * 2;
			}
		}

		if (0 <= inventory) {
			if (minTime > time || (minTime == time && bestHigh < targetHeight)) {
				minTime = time;
				bestHigh = targetHeight;
			}
		}
	}
	cout << minTime << " " << bestHigh;

	return 0;
}

 

 

후기

처음에는 시간을 최대한 절약하고 싶어서 현재 값으로 들어온 땅들을 바탕으로 정렬 후 반복문을 돌렸었는데. 로직이 훨씬 복잡해지고,
반례들도 상당히 많았었다.

문제의 접근 방식을 다르게 생각하는 능력을 길러야하는거 같다.