BOJ18111: 마인크래프트

작성일

https://www.acmicpc.net/problem/18111

  • 연휴동안 100문제 풀기 (4/100)
  • 차이를 최소로 하는 문제.
  • 처음에는 최대 256 높이 조건을 못보고 그냥 엄청 큰 높이로 가정하고 풀었다.
  • 여튼 되긴 된다. 사실은 완전탐색 문제.
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
#include <bits/stdc++.h>
using namespace std;

int N, M, B, sum, UB;
int arr[257];

int check(int h) {
  int ans = 0;
  for(int i = 0; i < 257; i++) {
    int diff = h - i;
    ans += (diff > 0 ? diff : -2 * diff) * arr[i];
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin >> N >> M >> B;

  sum = B;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      int tmp;
      cin >> tmp;
      sum += tmp, arr[tmp]++;
    }
  }

  int lb = 0, ub = min(sum / (N*M), 256);
  UB = ub;
  while (lb < ub) {
    int m = (lb+ub)/2;
    if(m == UB || check(m) < check(m+1)) ub = m;
    else lb = m+1;
  }
  cout << check(lb) << " " << lb;
}