BOJ 18111 마인크래프트

이 문제는 땅의 높이를 0~256중 하나로 하여 땅을 고르게 만들때 걸리는 시간과 땅의 높이를 출력하는 프로그램이다.

처음 생각한 방법은 같은 높이의 블록 갯수를 파악하여 {높이,갯수} 형태로 배열에 저장하고 이들중 하나의 높이로 통일 시킬 때 걸리는 시간과 높이를 구하여고 하였다.

 

하지만 위와 같은 방법의 문제점은 문제에서 주어진 높이로만 땅을 고르게 할때 다음과 같은 반례가 나올 수 있다.

 

1 3 1
1 4 1

 

다음과 같은 경우 정답은 6 2 가 되지만 처음 생각한 방법으로 구현 하였을 경우 배열에 {1,2},{4,1}이 들어가고 결과는 6 1 이 나오게 된다. 이는 문제에서 시간이 같다면 높이가 높은것을 구하라고 하는것을 빼먹은 것이다.

 

이를 해결하기 위해 모든 높이에 대해 걸리는 시간을 모두 구하고 이때 최소인 시간을 저장하여 문제를 해결하였다.

풀이는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>
#define INF 987654321;
using namespace std;

int n, m, b;
vector<int> v;
vector<pair<int, int>> compact_v; //{높이, 갯수}

void solution()
{
	int minWeight = INF;
	int height = 0;
	for(int i = 0; i <= 256; i++) // 높이 기준
	{
		int weight = 0;
		int block = b;
		for(int j = 0; j < compact_v.size(); j++)
		{
			if(i > compact_v[j].first)
			{
				int needBlock = (i - compact_v[j].first) * compact_v[j].second;
				block -= needBlock;
				weight += needBlock;
			}
			else if(i < compact_v[j].first)
			{
				int removeBlock = (compact_v[j].first - i) * compact_v[j].second;
				block += removeBlock;
				weight += (2 * removeBlock);
			}
		}
		if(block >= 0)
		{
			if(weight <= minWeight)
			{
				minWeight = weight;
				height = i;
			}
		}
	}
	cout << minWeight << " " << height;
}

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

	cin >> n >> m >> b;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			int num;
			cin >> num;
			v.push_back(num);
		}
	}

	sort(v.begin(), v.end());

	for(auto value : v)
	{
		if(compact_v.empty() || compact_v.back().first != value)
		{
			compact_v.push_back({ value,1 });
		}
		else
		{
			compact_v.back().second += 1;
		}
	}

	solution();
}