BaekJoon 18111번: 마인크래프트(C++)

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

18111번: 마인크래프트

풀이법

1) 시간초과를 고려하여 이분 탐색을 실시했으나 실패하여 BruteForce로 문제를 해결하였다.

2) 값을 입력 받음과 동시에 값 중 가장 작은 값과 가장 큰 값을 지정하였다.

3) 이후 for문을 통해 가장 작은 값 부터 가장 큰 값까지 search를 실시하여 가능한 경우의 수 중 가장 시간이 적게 걸리는 것과 그 중 가장 높이가 가장 높은 것을 출력하였다.

4) 이를 파악 시에는 인벤토리에 있는 블록의 개수가 0이 이상이고, 현재까지의 최소 값보다 새로 넣어본 값이 작거나 같은 경우 최소 시간과 높이를 갱신 시켜주었다. (for문을 낮은 높이에서부터 최대 높이 까지 돌렸기에 가능한 비교식이다.)

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

int n, m, b;
int arr[501][501];
int minVal = 1000000000;
int maxVal = 0;
int minSec= 1000000000;
int height = 0;
void check(int val)
{
	int nowD = b;
	int nowSec = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] > val)
			{
				nowD += arr[i][j] - val;
				nowSec += 2 * (arr[i][j] - val);
			}
			else if (arr[i][j] < val)
			{
				nowD -= val - arr[i][j];
				nowSec += val - arr[i][j];
			}
		}
	}
	if (nowD >= 0 && minSec >= nowSec)
	{
		minSec = nowSec;
		height = val;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> b;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] < minVal)
				minVal = arr[i][j];
			if (arr[i][j] > maxVal)
				maxVal = arr[i][j];
		}
	for (int i = minVal; i <= maxVal; i++)
		check(i);
	cout << minSec << " " << height;
}