18111번: 마인크래프트

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

18111번: 마인크래프트

1. 문제 분석

이 문제의 시간제한은 1초이고 N, M의 최댓값은 500, 500 높이의 범위는 0~256 이를 계산하면 257*500*500=64,250,000이다. 코드를 조금만 추가해도 1초가 넘어버리기 때문에 무식하게 풀면 안된다.

2. 코드 작성

#include <iostream>
#include <algorithm>
using namespace std;
int height[257];
pair<int, int> p_list[257];

bool comp(pair<int, int>& a, pair<int, int>& b)
{
	if (a.first == b.first) return a.second > b.second;//오름차순
	return a.first < b.first;//내림차순
	
}
int main()
{
	int M, N, B, cnt = 0;
	cin >> M >> N >> B;
	int num, max_num = -1;
	for (int i = 0;i < M;i++)
	{
		for (int j = 0;j < N;j++)
		{
			cin >> num;
			height[num]++;
			max_num = max(max_num, num);
		}
	}
	int sum_time = 0, sum_block = B;
	//0까지 다 깎음
	for (int i = 1;i <=max_num;i++)
	{
		if (height[i] != 0)
		{
			sum_time = sum_time + i * height[i] * 2;
			sum_block = sum_block + i * height[i];
		}
	}
	pair<int, int> p;
	p = { sum_time,0 };
	p_list[cnt++] = p;
	for (int i = 1;i <= max_num;i++)
	{
		for (int j = 0;j < i;j++) 
		{
			if (height[j] != 0)
			{
				sum_time = sum_time + height[j];
				sum_block = sum_block - height[j];
			}
		}
		for (int j = i;j <= max_num;j++)
		{
			if (height[j] != 0)
			{
				sum_time = sum_time - height[j] * 2;
				sum_block = sum_block - height[j];
			}
		}
		if (sum_block >= 0)
		{
			p = { sum_time,i };
			p_list[cnt++] = p;
		}
	}
	sort(p_list, p_list + cnt, comp);
	cout << p_list[0].first << " " << p_list[0].second;
	return 0;
}

3. 설명

그래서 나는 0~256에 집중했다.