#include <iostream>
#include <vector>
using namespace std;
int N, M, B;
int house[500][500];
int t1 = 2, t2 = 1; // 블록제거 : 2초, 블록쌓기 : 1초
int t = 99999999, line = 99999999; // 시간, 최대 높이
int main(int argc, char **argv){ //브루트포스 알고리즘
scanf("%d %d %d",&N,&M,&B); // 집터 크기와 블록 개수
int max = 0, min = 0;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> house[i][j]; // 집 입력 받기
if(max < house[i][j]){
max = house[i][j];
} else if(min > house[i][j]){
min = house[i][j];
} // 높이 최소, 최대값 찾기
}
}
for(int i=min; i<=max; i++){ // 해당 높이 사이
int remove = 0; // 블록 바로 빼면 뒤의 블록을 먼저 제거하는 경우를 고려하지 못한다.
int stack = 0;
for(int j=0; j<N; j++){
for(int k=0; k<M; k++){
if(house[j][k] > i){
remove += (house[j][k] - i); // 깎기
} else if(house[j][k] < i){
stack += (i - house[j][k]); // 채우기
}
}
}
if(stack <= remove + B){ // 깎아낸 것이 채우는 것보다 많을 때
int temp = remove * 2 + stack;
if(t > temp){
t = temp;
line = i;
} else if(t == temp){
line = i; // i는 계속 증가하므로 갱신만 시켜주면 됨
}
}
}
printf("%d %d", t, line); // 시간과 최대 높이 출력
return 0;
}
미루고 미뤘던 마인크래프트 브루트포스 문제를 풀었다.
한 줄 한 줄 구하면서 해당 높이에 해당하는 블록의 시간을 모두 구하면 된다. (브루트포스)
이런게 왜 이렇게 머릿속으로 쉽다는 것은 아는데 귀찮기 짝이 없는 것인지 모르겠다. 그래도 해야지 어쩌겠어...
주의할 점은 전체 깎을 블록과 채울 블록을 구한 다음에 시간을 계산해야한다는 것이다.
1 1 3 이렇게 되면 2칸을 만들기 위해서 가장 마지막의 블록 2개를 깎아낸 뒤 한 칸씩 쌓아주면 되기 때문이다.