백준 18111번 [마인크래프트](C++)-yes6686- 티스토리

백준 문제 풀이: 18111 [마인크래프트]

---

문제 링크: https://www.acmicpc.net/problem/18111

문제 설명:

마인크래프트에서 주어진 땅을 평탄화하는 작업을 수행합니다. 평탄화 후 모든 칸의 높이가 같아야 하며, 블록을 추가하거나 제거할 때 소요되는 시간이 다릅니다. 땅을 평탄화하는 데 걸리는 최소 시간을 구하고, 그러한 경우의 최대 높이를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[501][501];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, b;
    cin >> n >> m >> b;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];    
        }
    }

    int k;
    int time = 0;
    int mintime = 1e9;
    int maxheight = -1;

    for (int t = 0; t <= 256; t++) {
        time = 0;
        k = b;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] > t) {
                    time += (arr[i][j] - t) * 2;
                    k += (arr[i][j] - t);
                } else {
                    time += (t - arr[i][j]);
                    k -= (t - arr[i][j]);
                }
            }
        }
        if (k >= 0) {
            if (mintime >= time) {
                mintime = time;
                maxheight = t;
            }
        }
    }

    cout << mintime << ' ' << maxheight;
}

---

코드 설명

• 핵심 알고리즘: 모든 가능한 높이(0~256)를 검사하여 평탄화를 시도하고, 최소 시간을 계산합니다.
• 구현 세부사항:
  • 각 높이에 대해 현재 높이와 목표 높이의 차이를 계산합니다.
  • 블록을 제거하면 시간은 2초 증가하고 인벤토리에 블록이 추가됩니다.
  • 블록을 추가하면 시간은 1초 증가하고 인벤토리에서 블록이 소모됩니다.
  • 블록이 부족하면 해당 높이는 무시됩니다.
  • 최소 시간을 찾으면서, 동일한 시간일 경우 최대 높이를 갱신합니다.
• 시간 복잡도: O(256 × n × m)
  • 256개의 높이에 대해 각 칸을 검사하기 때문에 256 × n × m의 복잡도를 가집니다.

---

결과

주어진 입력에 대해 최소 시간으로 평탄화를 수행하며, 그러한 경우의 최대 높이를 출력합니다. 모든 가능한 높이를 검사하여 최적해를 찾는 브루트포스 방식으로 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!