[백준 18111] 마인크래프트 (C#, C++) - soo:bak

문제 링크

18111번 - 마인크래프트

설명

이 문제는 마인크래프트에서 지형을 평탄화하여 모든 칸의 높이를 동일하게 만드는 데 필요한 최소 시간과 그때의 높이를 구하는 문제입니다.

세로 N, 가로 M 크기의 집터에서 각 칸의 초기 높이가 주어지며, 인벤토리에 B개의 블록이 있습니다. 목표는 블록을 추가하거나 제거하여 모든 칸을 같은 높이로 만들되, 작업 시간을 최소화하는 것입니다.

작업 종류

• 블록 제거: 한 칸에서 블록을 하나 제거하여 인벤토리에 넣습니다. 이 작업은 2초가 소요됩니다.
• 블록 추가: 인벤토리에서 블록을 꺼내 한 칸 위에 쌓습니다. 이 작업은 1초가 소요됩니다.

제약 조건

• 사용할 수 있는 블록은 인벤토리에 있는 블록과 제거한 블록에 한정됩니다.
• 최종 높이는 0 이상 256 이하이어야 합니다.
• 가능한 작업 중 가장 짧은 시간이 소요되는 경우를 찾아야 하며, 만약 여러 높이가 동일한 시간이라면 가장 높은 높이를 선택해야 합니다.

---

접근법

• 높이는 0부터 256까지, 혹은 입력된 지형의 최솟값과 최댓값 사이를 전부 확인합니다.
• 각 가능한 높이 h에 대해 다음 작업을 수행합니다:
  • 모든 칸을 순회하며 현재 높이와 h의 차이를 계산합니다.
    • 현재 높이가 h보다 크면 블록을 제거하고, 제거한 블록 수와 시간(2초)을 누적합니다.
    • 현재 높이가 h보다 작으면 블록을 추가하고, 필요한 블록 수와 시간(1초)을 누적합니다.

  • 작업에 필요한 블록 수가 인벤토리에 있는 블록과 제거한 블록의 합보다 많으면 그 높이는 고려하지 않습니다.

    \[\text{neededBlock} \leq B + \text{removedBlock}\]
  • 가능한 경우에 대해서는 소요되는 시간을 계산하고, 가장 짧은 시간과 가장 높은 높이를 기록합니다.

---

Code

[ C# ]

using System;
using System.Linq;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
      var n = input[0], m = input[1], b = input[2];

      var ground = new int[n * m];
      var min = 256; var max = 0;

      for (int i = 0; i < n; i++) {
        var row = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
        for (int j = 0; j < m; j++) {
          var h = row[j];
          ground[i * m + j] = h;
          min = Math.Min(min, h);
          max = Math.Max(max, h);
        }
      }

      var bestTime = int.MaxValue;
      var bestHeight = 0;

      for (int h = min; h <= max; h++) {
        int add = 0, remove = 0;
        foreach (var g in ground) {
          if (g < h) add += h - g;
          else if (g > h) remove += g - h;
        }

        if (add > b + remove) continue;
        var time = add + 2 * remove;

        if (time < bestTime || (time == bestTime && h > bestHeight)) {
          bestTime = time;
          bestHeight = h;
        }
      }

      Console.WriteLine($"{bestTime} {bestHeight}");
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int len, width, inven;
  cin >> len >> width >> inven;

  int minT = 0;
  int nbGround = len * width;
  int* ground = new int[nbGround];
  for (int i = 0; i < nbGround; i++) {
    cin >> ground[i];
    minT += ground[i] * 2;
  }

  int maxHeight = -1;
  for (int height = 0; height <= 256; height++) {
    int cntAdd = 0, cntSub = 0;
    int block = inven;
    for (int i = 0; i < nbGround; i++) {
      if (ground[i] > height) {
        cntSub += ground[i] - height;
        block += ground[i] - height;
      } else if (ground[i] < height) {
        cntAdd += height - ground[i];
        block -= height - ground[i];
      }
    }
    if (block >= 0) {
      int time = cntAdd + 2 * cntSub;
      if (minT >= time) {
        minT = time;
        maxHeight = height;
      }
    }
  }

  cout << minT << " " << maxHeight << "\n";

  return 0;
}