백준 18111 S2 마인크래프트

문제: 마인크래프트

접근

우선 시간 제한이 1초이고, 메모리 제한은 1024MB이다.
가로 세로 최대 500 길이의 2차원 배열을 관리해야 할 것이고, 높이는 0부터 256까지 고정된 범위이다.
답으로는 최소 시간 뿐만 아니라, 그 때의 땅의 높이도 원한다.

완전 탐색으로 접근하는 것은 어떨까?

문제를 좀 훑어보니 일단 지문이 개 뚱뚱하고 조건이 꽤 복잡하다.

그리고 최적 시간과 높이를 계산해 내는 어떤 수학적 공식이 존재하는 것 같지도 않다. 어떻게 접근하건, 2차원 배열 전체를 몇 번 순회해야 하는 것은 마찬가지일 거라는 생각을 했다.

그러면 그냥 완전탐색으로 모든 가능한 높이별로 시간을 계산해보면 어떨까? 가 이 풀이의 핵심이었다. 당연히 가능성을 판단하기 위해 복잡도를 계산하였는데, 최대 256개 높이당 500x500 배열을 순회하므로 최악의 경우 $10^6$ 번의 연산을 하게 된다. 이 정도는 1초 안에 넉넉히 통과할 수 있다.

알고리즘

• 각 좌표의 블럭 높이를 입력받을 때, 최소 높이 min_height와 최대 높이 max_height를 계산한다.
• 출력할 최소 시간 min_time과 최적 높이 proper_height를 초기화 해둔다.
• 적절한 높이¹ 를 min_height이상, max_height의 어떤 값 c_height이라고 가정하고, 다음을 반복한다:
  • 격자 내 모든 블럭을 c_height로 만들기 위해 추가되어야 하는 블록의 개수 cnt_to_place와 제거되어야 하는 블록의 개수 cnt_to_remove를 계산한다.
  • 추가되어야 하는 블럭의 갯수가 인벤토리내의 블럭 갯수와 제거되어야 하는 블록의 개수의 합보다 크면, 현재 c_height를 무슨 수를 쓰더라도 못 만드는 것이다. 그러므로 다음으로 넘어간다.
  • c_height를 만들 수 있다면, 만들 때 걸리는 시간과 만들어진 높이를 계산하고, min_time과 proper_height와 비교해 갱신할 필요가 있으면 갱신한다.

코드

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

constexpr int TIME_REMOVE = 2;
constexpr int TIME_PLACE = 1;

int main() {
  // N, M in [1, 500] - 세로 가로
  // B in [0, 6.4 * 10^7] - 인벤토리 내 블록 수
  int N, M, B; cin >> N >> M >> B;

  vector<vector<int>> land (
    N, vector<int>(M, 0)
  );

  int min_height{0}, max_height{256};

  for (auto& hl: land) {
    for (auto& e: hl) {
      cin >> e;
      // 최대 높이와 최소 높이 갱신
      min_height = min(min_height, e);
      max_height = max(max_height, e);
    }
  }

  int min_time{numeric_limits<int>::max()};
  int proper_height{0};

  for (
    int c_height{min_height}; 
    c_height <= max_height; 
    ++c_height
  ) {
    int cnt_to_remove{0}, cnt_to_place{0};

    // 지금 높이에서 빼거나 추가해야 할 값 갱신
    for (auto& hl: land) {
      for (auto& e: hl) {
        int diff{e - c_height}; 

        // diff > 0 이면, 빼야 함
        if (diff > 0) {
          cnt_to_remove += diff;
        } else if (diff < 0) {
        // diff < 0 이면, 추가 해야 함
          cnt_to_place += -diff;
        }
      }
    }

    if (cnt_to_remove + B >= cnt_to_place) {
      int c_time{
        cnt_to_remove * TIME_REMOVE + cnt_to_place * TIME_PLACE
      };

      if (
        c_time < min_time || 
        (c_time == min_time && c_height > proper_height)
      ) {
        min_time = c_time;
        proper_height = c_height;
      }
    }
  }

  cout << min_time << ' ' << proper_height << '\n';
}

기타

• 중괄호 초기화의 모든 것