[백준알고리즘] 18111번: 마인크래프트 -C++

[백준알고리즘] 18111번: 마인크래프트 -C++

18111번: 마인크래프트 (acmicpc.net)

18111번: 마인크래프트

실버 문제 치고는 정답률이 낮다. 문제를 풀면서 그럴만하다고 느낀 게 실수하기 쉬운 부분이 있다. 다만 어려워서 그런 것은 아니기 때문에 반례도 생각하면서 풀어보면 좋을 문제다.

나는 생각한 반례도 다 돌아는 갔는데.. 통과를 못해서 반례 모음이 올라온 것을 보고 잘못된 부분을 찾을 수 있었다.

 

그리고 최대한 함수를 작게 나눠서 작성하고 있는데, 확실히 오류 찾기도 쉽고 수정하기도 쉬운 것 같다. 여기서는 아래 코드의 함수를 좀 더 순서를 정리하면 좋았을 것 같긴 한데 노트북으로 작성 중이라 보기 어려워서 생략했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

평탄화 작업을 수행할 때, 걸리는 시간이 가장 작은 높이를 구하는 문제다. 이때 시간이 같은 경우에는 보다 높은 높이로 정한다.

 

문제에서는 잔여 블럭의 수를 고려해야 한다. 블록 수가 부족하다면, 쌓지 못해 높은 높이로 평탄화 작업을 수행할 수 없다.

 

따라서, 나는 블럭을 깎는(dig) 작업을 먼저 수행했다. 깎아 얻은 블록까지 최종적으로 남은 블록을 이용해 같은 높이로 쌓을 수 있는지 판단했다.

 

어차피 최적의 시간은 현재 주어진 땅의 높이의 최소에서 최대 사이의 높이로 평탄화 작업을 수행할 때이기 때문에, 그 사이에서 가장 최적의 시간을 구했다. 목표 높이를 최소 높이에서 최대 높이로 높여가면서 확인을 했다.

코드에서는 적용하지 않았지만, 중간에 쌓을 블럭이 부족해 평탄화 작업을 수행하지 못하면 그 이상의 높이는 수행하지 않도록 수정해도 괜찮을 것 같다. 보다 높은 높이를 목표로 하면 땅을 파서 얻는 잔여 블록의 수가 더 줄지만, 쌓기 위해 필요한 블록의 수는 더 늘어나기 때문이다.

 

아래는 문제를 해결한 소스코드다. 클래스로 나누거나 함수 순서 정리가 안 돼서 보기 어려울 수는 있지만, IDE로 복사해서 보면 좀 더 편히 볼 수 있을 것 같다.

#include <cstdio>
#include <climits>
#include <map>

#define TIME_ITEM std::pair<int, int>

void minecraft();
void inputBlocks();
void inputAreaSize();
void inputInventory();
const int getAreaSize(const int iWidth, const int iDepth);
void inputHeights(const int iArea);
void leveling();
const int getLowestHeight();
const int getHighestHeight();
int leveling(const int iLowest, const int iHighest, const int iTarget);
TIME_ITEM dig(const int iHighest, const int iTarget);
int calculateDigTime(const int iBlockCount);
TIME_ITEM stack(const int iLowest, const int iTarget, int iItems);
int calculateStackTime(const int iBlockCount);
int getTargetBlockCount(const int iHigherHeight, const int iLowerHeight);
void printHighestFlattenGround();

const int iHeightMaximum = 256;
int iGroundWidth = 0;
int iGroundDepth = 0;
int iInventoryItems = 0;
unsigned int arrHeightPoints[iHeightMaximum + 1] = { 0, };
int iBestWorkTime = INT_MAX;
int iBestHeight = 0;

int main(void) {
	minecraft();

	return 0;
}

void minecraft() {
	inputBlocks();
	leveling();
	printHighestFlattenGround();
}

void inputBlocks() {
	inputAreaSize();
	inputInventory();

	const int iAreaSize = getAreaSize(iGroundWidth, iGroundDepth);

	inputHeights(iAreaSize);
}

void inputAreaSize() {
	scanf("%d", &iGroundDepth);
	scanf("%d", &iGroundWidth);
}

void inputInventory() {
	scanf("%d", &iInventoryItems);
}

const int getAreaSize(const int iWidth, const int iDepth) {
	return iWidth * iDepth;
}

void inputHeights(const int iAreaSize) {
	for (int iCnt = 0; iCnt < iAreaSize; ++iCnt) {
		int iHeight = 0;
		scanf("%d", &iHeight);
		arrHeightPoints[iHeight]++;
	}
}

void leveling() {
	const int iLowest = getLowestHeight();
	const int iHighest = getHighestHeight();

	for (int iHeight = iLowest; iHeight <= iHighest; ++iHeight) {
		int iWorkTime = leveling(iLowest, iHighest, iHeight);
		if (-1 == iWorkTime) {
			continue;
		}

		if (iBestWorkTime >= iWorkTime) {
			iBestWorkTime = iWorkTime;
			iBestHeight = iHeight;
		}
	}
}

const int getLowestHeight() {
	for (int iPoint = 0; iPoint <= iHeightMaximum; ++iPoint) {
		if (0 < arrHeightPoints[iPoint]) {
			return iPoint;
		}
	}

	return 0;
}

const int getHighestHeight() {
	for (int iPoint = iHeightMaximum; iPoint >= 0; --iPoint) {
		if (0 < arrHeightPoints[iPoint]) {
			return iPoint;
		}
	}

	return iHeightMaximum;
}

int leveling(const int iLowest, const int iHighest, const int iTarget) {
	int iItems = iInventoryItems;

	// [TEST]
	if (iTarget == 35) {
		iItems = iInventoryItems;
	}

	TIME_ITEM pairDigResult = dig(iHighest, iTarget);
	const int &iDigTime = pairDigResult.first;
	iItems += pairDigResult.second;

	TIME_ITEM pairStackResult = stack(iLowest, iTarget, iItems);
	if (0 > pairStackResult.first) {
		return -1;
	}
	const int &iStackTime = pairStackResult.first;
	
	return iDigTime + iStackTime;
}

TIME_ITEM dig(const int iHighestHeight, const int iTargetHeight) {
	int iTimes = 0;
	int iItems = 0;

	for (int iHeight = iHighestHeight; iHeight > iTargetHeight; --iHeight) {
		const int iDigTargetBlocks = getTargetBlockCount(iHeight, iTargetHeight);
		if (0 == iDigTargetBlocks) {
			continue;
		}

		iTimes += calculateDigTime(iDigTargetBlocks);
		iItems += iDigTargetBlocks;
	}

	return std::make_pair(iTimes, iItems);
}

int calculateDigTime(const int iBlockCount) {
	return (2 * iBlockCount);
}

TIME_ITEM stack(const int iLowestHeight, const int iTargetHeight, int iRemainItems) {
	int iTimes = 0;
	int iItems = iRemainItems;

	for (int iHeight = iLowestHeight; iHeight < iTargetHeight; ++iHeight) {
		const int iStackTargetBlocks = (-1) * getTargetBlockCount(iHeight, iTargetHeight);
		if (0 == iStackTargetBlocks) {
			continue;
		}

		// 쌓을 블럭이 부족함
		if (iStackTargetBlocks > iItems) {
			return std::make_pair(-1, -1);
		}

		iTimes += calculateStackTime(iStackTargetBlocks);
		iItems -= iStackTargetBlocks;
	}

	return std::make_pair(iTimes, iItems);
}

int calculateStackTime(const int iBlockCount) {
	return iBlockCount;
}

int getTargetBlockCount(const int iCurrentHeight, const int iTargetHeight) {
	int iBlockCount = (int) arrHeightPoints[iCurrentHeight];
	if (0 == iBlockCount) {
		return 0;
	}

	return (iCurrentHeight - iTargetHeight) * iBlockCount;
}

void printHighestFlattenGround() {
	printf("%d %d", iBestWorkTime, iBestHeight);
}