[C++] 18111 : 마인크래프트

실버 Ⅲ

 

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector <vector<int>> world;
int N, M, B;

int main() {
	scanf("%d%d%d", &N, &M, &B);

	int tmp;
	int mi = 501;
	int ma = -1;

	world.resize(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &tmp);
			world[i][j] = tmp;
			if (tmp < mi) mi = tmp;
			if (tmp > ma) ma = tmp;
		}
	}

	vector <pair<int, int>> times;
	for (int level = mi; level <= ma; level++) {

		int t = 0;
		int needed = 0;
		int got = B;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {

				if (world[i][j] > level) {
					t += (world[i][j] - level) * 2;
					got += (world[i][j] - level);
				}
				else if (world[i][j] < level) {
					t += (level - world[i][j]);
					needed += (level - world[i][j]);
				}
			}
		}
		if (got >= needed) times.push_back({level, t});
	}
	
	int ans = times.front().second;
	int idx = 0;

	for (int i = 0; i < times.size(); i++) {
		if (times[i].second < ans) {
			ans = times[i].second;
			idx = times[i].first;
		}
		else if (times[i].second == ans && idx < times[i].first) idx = times[i].first;
	}


	printf("%d %d", ans, idx);
}

 

 

맨 마지막의 for문에서

조금 단순하게 해 본다고 이렇게 했었다

 

	//level이 높은 경우가 우선시 되도록 times의 벡터 뒷부분부터 탐색을 시작한다

	for (int i = times.size() - 1; i >= 0; i--) {
		if (times[i].second < ans) {
			ans = times[i].second;
			idx = times[i].first;
		}
	}

 

이랬더니 틀렸습니다가 떠서.. 코드를 아무리 뜯어봐도 틀릴 부분이 여기밖에 없길래 설마 하고 고쳤더니 맞았다

아직도 왜인지는 모름.. 무슨 반례가 있을까?

 

아 그리고 엄청난 사실이 하나 있는데

사실 이차원 벡터를 만들지 않아도 된다

 

문제를 풀 때 이차원인 성질을 전혀 활용하지 않기 때문에...(필요 없다)

그냥 높이들의 정보를 저장할 집합을 하나 만들어 주면 된다

 

문제 푸는데 필요한 알고리즘은.. 브루트 포스다

 

암튼 이 문제로 2 클래스 40문제인가 다 풀어서 ++을 달았다

2++ 다는 것보다 그냥 클래스 3을 다는 게 공부에는 효과가 더 좋겠지만..

애초에 이것도 강의 안 듣고 하는 거라 클래스 3 풀려면 너무 오래 걸려서 학업에 지장을 준다ㅋㅋ

이제 클래스 3 풀어야 하는데 이건 그 주에 필요한 과제 다 미리 하고 공부까지 미리 해 놓으면 하도록 하자

이렇게 안 해놓으면 맨날 천날 백준 붙들고 있을 듯...ㅋㅋ

 

 

( + ㅋㅋㅋ 사실은 백준 레이팅 시스템이 바뀌어서 class 2++로 올라가면 점수 좀 오르려나 하고 한 거긴 한데

클래스 점수는 2나 2+이나 2++이나 똑같다ㅋㅋ꼼수부렸는데 안 통했네~~~ 아코~~)