Koala - 12기/코딩테스트 준비 스터디
[백준/C++] 18111번: 마인크래프트
Langerak
2023. 9. 10. 16:28
문제
설명
블럭을 쌓거나 제거해서 평평한 바닥을 만들면 되는 문제이다.
입력되는 땅의 높이가 0~256 사이라서 0과 256 사이의 높이를 모두 체크해도 되지만,
입력된 높이의 최소~최대 사이만 체크해도 가능하다.
답이 여러개라면 가장 땅의 높이가 높은 것을 출력해야 하기에 낮은 높이부터 체크하였다.
각 높이를 돌면서, 평평하게 만드는데 드는 시간과 블럭을 체크하였고, 블럭이 부족하다면 답으로 기록하지 않았다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;
int N, M, B;
int arr[500][500];
int answer_time = INT_MAX;
int answer_height;
int main() {
cin >> N >> M >> B;
int min = INT_MAX, max = INT_MIN;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
if (arr[i][j] > max) max = arr[i][j];
if (arr[i][j] < min) min = arr[i][j];
}
}
for (int height = min; height <= max; height++) {
int time = 0;
int block = B;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] > height) {
time += abs(arr[i][j] - height) * 2;
block += abs(arr[i][j] - height);
}
else if (arr[i][j] < height) {
time += abs(arr[i][j] - height);
block -= abs(arr[i][j] - height);
}
}
}
if (answer_time >= time && block >= 0) {
answer_time = time;
answer_height = height;
}
}
cout << answer_time << " " << answer_height;
return 0;
}