백준 18111번 마인크래프트 (C++) 🚩

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

18111번: 마인크래프트

 

주의할점은 인벤토리 b가 중간에 마이너스가 되든 상관없다는것이다. 그건 순서의 문제니까 최종이 음수가 안되기만 되면 되는것!!

#include <iostream>
#include<vector>
#include<map>

using namespace std;

vector<vector<int>>arr;
vector<int>info;
int n,m,b;

 long long cal(int num,int b){
  long long cnt=0;    
  
  for(int i=0;i<info.size();i++){
      if(i>num){
          cnt+=(i-num)*2*info[i];
          b+=info[i]*(i-num);
      }
      if(i<num){
          cnt+=(num-i)*info[i];
          b-=info[i]*(num-i);
      }
      // if(b<0)return -1; 왜안되는데? 
   }
   
   if(b<0)return -1;

   return cnt;    
    
    
}

int main()
{
   
   int cnt=0; 
  
   //제거 2초 올려놓기 1초 
   info.assign(257,0);
   cin>>n>>m>>b;
   

   arr.assign(n,vector<int>(m,0));
   
   int mins=10000000;
   int maxs=0;
   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           cin>>arr[i][j];
           mins=min(mins,arr[i][j]);
           maxs=max(maxs,arr[i][j]);
           info[arr[i][j]]++;
       }
   }
   //제거*2 올리기 +1 
   
   if(mins==maxs){ //처음부터 고른경우 
       cout<<0<<' '<<mins;
       return 0;
   }
   
   
   int h=0; 
   long long ans=100000000000;
   
   for(int i=mins;i<=maxs;i++){
       
       long long t=cal(i,b); //i높이에서 걸리는 시간 
       
       if(t>0){ //b가 양수일때만 
           if(ans>t){
               ans=t;
               h=i;
           }
           else if(ans==t){
               if(i>h){
                   h=i; //시간이 같으면 더 높은 위치 
               }
           }
       }
       
       
   }
 
   cout<<ans<<' '<<h;

    return 0;
}