[C++] 백준 18111번: 마인크래프트

18111번: 마인크래프트

문제 바로가기

이 문제 걸핏보면 어려워 보이지만 처음 구현했을 때는 술술 나올 정도로 어렵진 않았다.

알고리즘 분류가 브루트포스 알고리즘으로 돼 있길래, 맘 편하게 코드를 짰다.

worst case도 입력해주며 코드를 고쳐나갔다.

누락됐던 블럭을 부수면 인벤토리에 블럭을 추가하는 것도 추가시키고,

블럭이 지금 모자르다고 바로 break를 걸었던 것도 최종 결과에 따라 반영했다.

인벤토리에 블럭을 증가/감소시킨 양 만큼 변화하도록 수정하는 등 다양한 수정을 거쳤다.

코드에 주석까지 하나하나 달아가며 검토했지만,

제출한 코드의 결과는 "틀렸습니다"

아래가 해당 코드다.

#include <cstdio>
#include <algorithm>

int main()
{
	int N, M, B;
	scanf("%d %d %d", &N, &M, &B);
	int* ground = new int[N * M];
	for (int i = 0; i < N * M; i++)
		scanf("%d", ground + i);

	int topmost = *std::max_element(ground, ground + N * M);
	int lowest = *std::min_element(ground, ground + N * M);
	long long * costs = new long long[topmost - lowest + 1];
	for (int floor = 0; floor < topmost - lowest + 1; floor++) {
		int current_height = lowest + floor;
		int remain = B;
		costs[floor] = 0;
		for (int i = 0; i < N * M; i++)
			if (ground[i] > current_height) {
				costs[floor] += 2 * ((long long)ground[i] - current_height);
				remain++;
			}
			else if (ground[i] < current_height) {
				remain--;
				costs[floor] += 1 * (current_height - ground[i]);
			}
		if (remain < 0)
			costs[floor] = -1;
	}
	long long minimum_cost = std::numeric_limits<long long>::max();
	int best_height = 0;
	for (int i = 0; i < topmost - lowest + 1; i++) {
		if (costs[i] <= minimum_cost && costs[i] != -1) {
			minimum_cost = costs[i];
			best_height = lowest + i;
		}
	}
	printf("%lld %d\n", minimum_cost, best_height);
	delete[] ground;
	return 0;
}

그리고 위에서 minimum_cost와 best_height를 찾는 과정을 각 높이별 소요시간을 계산할 때 한 번에 구하고,

minimum_cost가 불필요하게 long long 형식으로 되어있던 것을 int형으로 바꾸었다.

또한, std::min_element, std::max_element로 최소, 최댓값을 구했던 것을 각각 문제에서 주어진 한계치인 256, 0으로 대입했고, std::numeric_limits<int>::max()는 주어진 조건 내 가능한 최대 값인 2 * 256 * 250000으로 바꾸었다.

#include <cstdio>

int main()
{
	int N, M, B;
	scanf("%d %d %d", &N, &M, &B);
	
	int* ground = new int[N * M];
	int topmost = 0;
	int lowest = 256;
	for (int i = 0; i < N * M; i++) {
		scanf("%d", ground + i);
		if (ground[i] > topmost)
			topmost = ground[i];
		if (ground[i] < lowest)
			lowest = ground[i];
	}

	int minimum_cost = 128000000;
	int best_height = 0;
	for (int height = lowest; height <= topmost; height++) {
		int remain = B;
		int cost = 0;

		for (int i = 0; i < N * M; i++) {
			if (ground[i] > height) {
				cost += 2 * (ground[i] - height);
				remain += ground[i] - height;
			}
			else if (ground[i] < height) {
				cost += height - ground[i];
				remain -= height - ground[i];
			}
		}

		if (remain < 0)
			continue;

		if (cost <= minimum_cost) {
			minimum_cost = cost;
			best_height = height;
		}
	}

	printf("%d %d\n", minimum_cost, best_height);
	delete[] ground;
	return 0;
}

위 코드가 수정사항을 반영한 코드이다. 훨씬 간결해졌다.

이를 제출하니 "맞았습니다!!"가 뜨긴 하지만, 기존 것이 왜 틀렸는지는 잘 모르겠다.