백준 18111번 C++

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

18111번: 마인크래프트

이번에는 문제가 생각보다 어려운 문제였습니다.

알고리즘이 어려웠다기 보다는 푸는 방식에 대한 생각을 요구하는 문제였습니다.

 

저는 이 풀이 과정을 생각하게 된 계기는 숫자가 예시에서 63, 64로 너무 크게 나와서 숫자를 줄이면 더 쉽게 풀 수 있을 것이라는 생각이 들어서 landMin을 구한 다음에 모든 곳에서 뺐습니다.

여기서부터 문제의 풀이가 시작이 되었습니다.

 

결국에 제일 적게 드는 시간을 구해야하기 때문에 가장 낮은 높이를 구해도 landMin일 것입니다.

그리고 인벤토리에 블럭이 많아서 다 쌓기만해도 가장 높은 높이는 landMax가 될 것입니다.

이 생각으로 범위를 정해서 for문을 돌려보았습니다.

 

하나의 문제점은 인벤토리 내의 블럭의 갯수였는데 이것을 remove + b를 통해 build보다 크면 시간과 높이를
갱신하는 방식으로 진행하였습니다.

 

#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;

/*
	1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
	2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
	1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 최소 시간.
*/

int land[501][501] = { 0, };

int main() {
	int n, m; //n은 세로, m은 가로, b는 현재 가지고 있는 블럭의 갯수
	double b;
	cin >> n >> m >> b;

	int maxTime;
	int landMin = 267; int landMax = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> land[i][j];			
				if (land[i][j] > landMax) {
					landMax = land[i][j];
				}
				else if (land[i][j] < landMin) {
					landMin = land[i][j];
				}			
		}
	}

	int height, resultHeight = 267, time, minTime = 2147483646;
	int remove = 0, build = 0;

	for (int k = landMin; k <= landMax; k++) {			//<=을 해줘야한다. min일때 그리고 max일때 둘다 비교해야하기 때문이다.
		remove = 0; build = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				height = land[i][j] - k;					//land에서 k를 빼서 얼만큼 올리고 또는 내려야하는지 찾는다. 어느 높이가 적정 높이인지 모르기 때문에 돌아가면서 찾는다

				if (height > 0) {							//height가 높으면 블록 부순다
					remove += height;
				}
				else if (height < 0) {						//낮으면 블록 넣는다.
					build -= height;
				}
			}
		}

		if (remove + b >= build) {			//이 if문이 성립을 해야 완성이 된다는 의미이다. 그래서 이 이후에 시간을 구해준다.
			time = remove * 2 + build;

			if (time <= minTime) {			//최소 시간을 구해야하기 때문에 작성 <=인 이유는 resultHeight를 높여주기 위해서이다.
				minTime = time;
				resultHeight = k;
			}
		}
	}

	cout << minTime << " " << resultHeight << endl;
}