백준 18111번 : 마인크래프트

문제 접근

---

1. 입력을 굳이 2차원 배열로 받을 필요가 없다고 생각했다.
   
     높이 데이터만 갖고, 답을 찾을 수 있기 때문에 입력으로 높이 값만 받았다.
   
   
2. 범위를 지정하고, 무조건 성립하는 개념을 찾았다.
   
     우선 가장 낮은 높이와 가장 높은 높이라는 정답이 나올 수 있는 범위를 지정했다. 그 뒤 일단 가장 낮은 높이까지 인벤토리에 넣은 뒤에 한 칸씩 기준을 올렸을 때, 시간 변화량이 양수가 되면 바로 전 높이가 최단 시간, 최대 높이라는 걸 알 수 있었다.
   
     그 이유는 간단하다. 문제의 조건 중 하나가 '집터 아래에 빈 공간이 존재하지 않는다.'이기에, 바로 위 높이의 블록 개수는 지금보다 많을 수 없다. 따라서 현재 높이의 블록 개수만큼 '넣기'를 취소하고, 빈 공간만큼 '꺼내기'를 했을 때의 시간 변화량이 양수라면, 그 위 높이의 시간 변화량도 양수일 수밖에 없다.
   
     그렇기에 나는 일단 최저 높이까지 넣은 뒤, 한 칸 씩 높이며 시간 변화량을 확인하는 방법으로 풀었다.

 

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

18111번: 마인크래프트

 

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, B, input, max_height = -1, min_height = 257, dtime, ans_time, ans_height;
	vector<int> height_count(257, 0);


	cin >> N >> M >> B;

	for (int i = 0; i < N * M; ++i)
	{
		cin >> input;

		for(int j=0; j<=input; ++j)
			++height_count[j];

		if (min_height > input)
			min_height = input;

		else if (max_height < input)
			max_height = input;
	}


	ans_time = 0;

	ans_height = min_height;

	for (int check_height = min_height + 1; check_height <= max_height; ++check_height)
	{
		ans_time += height_count[check_height] * 2;
		B += height_count[check_height];
	}


	for (int check_height = min_height + 1; check_height <= max_height; ++check_height)
	{
		if (B - N * M < 0)
			break;

		B -= N * M;

		dtime = -2 * height_count[check_height] + 1 * (N * M - height_count[check_height]);

		if (dtime > 0)
			break;

		ans_time += dtime;
		ans_height = check_height;
	}


	cout << ans_time <<' '<< ans_height << '\n';

	return 0;
}

 

 

 

느낀 점

---

    이번 문제는 입력 값이 크지 않아서 O(n^2)으로 풀어도 되는 문제다. 그런데 괜히 오기로 O(n)으로 풀 수 있을 것 같아서 삽질하다가 머리 아파서 포기했다.. O(n)으로 푸는 방법은 높이 데이터를 받을 때, 어떤 높이에 몇 개의 블록이 있는지 다 채우지 않고, 그냥 최종 높이만 가지고 푸는 방법이다. 그냥 주어진 조건대로 깔끔하게 하는 게 최선인 것 같다. 아직 많이 부족한 만큼 맨땅에 삽질을 하지 말고, 정답이 있는 삽질을 하도록 하자.

 

 

1. 변수의 이름을 잘 설정하고, 개념을 명확히 인지하자.
   
     누누이 강조하는 것!
   
   
2. 최적의 선택을 하자.
   
     문제를 보고 가장 좋은 방법이 있음에도 굳이굳이 안 하며 삽질을 했다. 고집부리지 말고 최적의 선택을 하자.
   
   
3. 코드가 제대로 동작하지 않는다면, 영역 별로 확인해보자.
   
     당연한 소리이지만, 코드에서 기능별로 영역을 나누어 하나씩 확인해 보며 문제 되는 부분을 찾아보는 게 가장 확실한  문제 해결 방법이다. 경찰이 수사망을 좁혀가듯이 말이다.
   
   
4. 필요한 정보를 정리하고, 절대적인 명제를 만들어보자.
   
     문제의 정답이 나올 수 있는 범위를 지정하거나, 시간 변화량이 늘어나면 이후도 늘어날 수밖에 없다는 사실 등과 같이 문제에 주어진 조건으로 절대적인 명제를 만들어보고, 이를 기준으로 문제를 풀이해 보자.

 

 

인생이란.. 삽질의 연속..