BOJ. 18111

#BOJ18111

마인크래프트

이 문제는 사실 어제 해결했는데 세상에 이렇게 반례가 많이 나오는 문제는 처음 봤다. 진짜 다 풀었다고 생각한 순간이 한 세 번은 온 거 같았는데 다 틀렸었다. 그럼 이 문제를 해결하는 방법에 대해서 이야기해 보자. 이 문제는 단순하게 생각하면 브루트 포스를 이용하면 된다. 최저층과 최고층을 구한 후 각 층마다 얼마나 블록을 변환해야 되는지 정하고, 이를 인벤토리에 맞게 비교하면 된다. 이 인벤토리를 고려하는 과정이 생각보다 엄청나게 오류를 많이 유발시킨다. 왜냐하면 다른 블록에서 꺼낸것을 다른 곳에 붙이는 과정도 생각할 수 있는데 이 예제가 예제에는 제시가 되어 있지 않아서 단순하게 생각하고 제출하면 틀렸습니다. 지옥을 맞볼 수 있다. 코드가 좀 더럽지만 참고한다면 많은 도움이 될 것이다.

# include <iostream>
# include <algorithm>
using namespace std;

bool compare(int a, int b){
   return a > b;
}

int main(){
   ios_base::sync_with_stdio(false);
	cin.tie(0);

   int N, M, height;
   long long B, num;
   cin >> N >> M >> B;
   num = N * M;
   int* arr = new int[num];
   for (long long i = 0; i < num; i++){
       cin >> arr[i];
   }
   sort(arr, arr + num, compare);
   int ans = 2147483000;
   for (int i = arr[num - 1]; i <= arr[0]; i++){
       int inven = B, height_temp = i, ans_temp = 0;
       for (long long j = 0; j < num; j++){
           int temp = arr[j] - i;
           if (temp > 0){
               inven += temp;
               ans_temp += temp * 2; 
           }
           else{
               inven += temp;
               ans_temp -= temp;
           }
           if (inven < 0){
               ans_temp = 2147483000;
               break;
           }
       }
       if (ans != min(ans, ans_temp)){
           ans = ans_temp;
           height = height_temp;
       }
       if (ans == ans_temp && height != height_temp){
           height = height_temp;
       }
   }   
   cout << ans << " " << height;
}