Even Idiots Can Make Game

백준 18111 S2 마인크래프트

Date/Lastmod
Section
PS
Title
백준 18111 S2 마인크래프트
Ps-Tags
Solved
03-11/25

#1 접근

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

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

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

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

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

#1 알고리즘

#1 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#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';
}

#1 기타

  1. 최소 시간을 보장하는 높이 ↩︎

comments powered by Disqus