백준 18111번 c++ 풀이

안녕하세요 오늘은 마인크래프트라는 게임에 있는 상황을 재연한 아주 재밌는 문제를 풀어보도록 하겠습니다.

 

전략:

1. 있는 블록중에 최소와 최대를 구하고 그 값들과 그 사이를 반복하는 for문을 만듭니다.

2. for문의 변수인 tc를 각 블록과 차이를 구해서 차이가 양수이면 제거해야하므로 2를 곱해서  pair의 first에 더해줍니다. 음수일떄는 block변수에 그 값만큼 빼줍니다.

3. 결과적으로 block이 음수이면 안되는 코드이므로 continue해주고 그것이 아니라면 result vector에 pair를 대입해줍니다.

4. 마지막에 comp라는 함수를 기반으로 result를 sort하여서 시간이 같을 때 높이 가 큰 순으로 정렬하는 코드를 짭니다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
int comp(pair<int, int>a, pair<int, int>b){
	if(a.first == b.first){
		return a.second > b.second;
	}
	else{
		return a.first<b.first;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, B;
	cin>>N>>M>>B;
	vector<vector<int>>v(N, vector<int> (M));
	int min = 258, max = -1;
	for(int i= 0;i<N; ++i){
		for(int j= 0; j<M; ++j){
			int x;
			cin>>x;
			if(max<x){
				max = x;
			}
			if(min>x){
				min = x;
			}
			v[i][j] = x;
		}
	}
	//제일 작은것부터 큰거 맞춰보기
	vector<pair<long long int, int>> result;
	
	for(int tc= min; tc<=max; tc++){
		int block = B;
		pair<long long int, int> p(0, 0);//first가 time, second가 height

		for(int i= 0; i<N; ++i){
			for(int j= 0; j<M; ++j){
				int h = v[i][j];
				int mi = h-tc;
				if(mi>0){
					p.first+= 2 * mi;				
					block+=mi;
				}
				else if(mi<0){
					p.first += (-1) * mi;
					block += mi;
				}
			}
			
		}
		if(block>=0){
			p.second =tc;
			result.push_back(p);
		}
	}
	sort(result.begin(), result.end(), comp);
	cout<<result[0].first<<" "<<result[0].second<<"\n";
}