컴퓨터 사이언스/1고리즘
백준 18111 : 마인크래프트
저세상 개발자
2021. 9. 16. 23:40
https://www.acmicpc.net/problem/18111
가로, 세로 500, 최대 높이가 256이므로 500 x 500 x 256 = 64,000,000 으로 브루트포스로 해결할 수 있는 문제다.
#include <iostream>
#define max(a,b) a>b?a:b
using namespace std;
int n, m, b;
int board[500][500];
void solution() {
int height = 0;
int cur_time, curb, min_time, min_height, req;
bool flag;
cin >> n >> m >> b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
height = max(height, board[i][j]);
}
}
min_time = 1e9;
while (height >= 0) {
cur_time = 0, curb = b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] <= height) continue;
req = board[i][j] - height;
cur_time += 2 * req;
curb += req;
}
}
flag = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] >= height) continue;
req = height - board[i][j];
if (curb < req) { cur_time += 1e9; flag = 1; break; }
cur_time += req;
curb -= req;
}
if (flag) break;
}
if (cur_time < min_time) {
min_time = cur_time; min_height = height;
}
--height;
}
cout << min_time << ' ' << min_height << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solution();
return 0;
}
메모리: 2996 kb | 시간: 224 ms |