이번 문제는 백준의 실버 2 문제 마인크래프트이다.
실버 문제지만 실버 문제 중에서도 어려운 문제가 있다.
한 번 차근차근 문제를 읽어보자.
땅을 파거나, 블록을 설치해 땅을 평평하게 만들어달라고 한다.
땅의 크기는 최대 500 X 500 크기가 될 수 있고,
각 땅의 높이는 최대 256, 블록은 6.4 X 10^7개를 가질 수 있다.
땅을 파는 데에는 2초, 블록을 설치하는 데에는 1초가 걸린다.
실제 마인크래프트에 걸려있는 조건과 유사한 조건이다, 꽤 재밌는 문제 같다.
어떤 식으로 문제에 접근해야 할까?
일단 완전탐색을 해야 하는 문제임에는 틀림 없는 것 같다.
어떤 방식으로 맵을 완전탐색 해야 할까?
재귀 방식?
2차원 배열을 모두 훑으며, 최소로 시간이 드는 경우를 찾아야 한다.
그럼 땅을 팔 때, 블록을 설치할 때로 구분하여 재귀적으로 맵을 훑는건 어떨까?
그랬다간 Stack overflow나 시간 초과가 발생하게 될 것 같다.
250000칸을 모든 경우에 대해 일일이 재귀적으로 탐색하는 것은 힘들다고 생각한다.
그냥 for문
그럼 어차피 2차원 배열을 훑어서 최소치를 찾아야 하고,
최고 높이도 256칸 까지 밖에 안되니, 그냥 모든 가능한 높이를 다 훑어보는건 어떨까?
0부터 256까지 가능한 높이를 모두 훑어보며, 값을 매긴다면?
O(250000 * 256) 일테니 6400만으로, 1초도 걸리지 않고 충분히 훑을 수 있다.
각 칸에 대해서, 높이 차가 양수면 쌓고 음수면 깎아야 한다.
이 때, 쌓을 땐 인벤토리에서 빼주고 깎을 땐 인벤토리에 블록 만큼 추가해준다.
최종적으로, 각 칸에서 쌓고 깎은 점수를 답에 X1, X2하여 더해준다.
전체 구현 코드는 아래와 같다.
for (int i = 0; i <= 256; i++) {
int pile = 0;
int dig = 0;
int inven = blocks;
int partial_answer = 0;
for (int j = 0; j < row; j++) {
for (int k = 0; k < col; k++) {
if (i - minecraft_map[j][k] > 0) {
// 높이의 차이가 양수면 쌓아야 함
pile += (i - minecraft_map[j][k]);
inven -= (i - minecraft_map[j][k]);
}
else {
// 높이의 차이가 음수면 깎아야 함
dig += (minecraft_map[j][k] - i);
inven += (minecraft_map[j][k] - i);
// 중요한 것은 깎으면 인벤토리에 넣을 수 있음!!
}
}
}
if (inven < 0)
continue;
partial_answer += (pile + (dig * 2));
if (answer >= partial_answer) {
// i가 뒤로 갈수록 커지므로, 등호가 필요함
answer = partial_answer;
max_height = i;
}
}사실 처음에 문제를 잘못 읽어서 깎을 때 블록을 가져갈 수 있는지 몰랐다.
그 부분 때문에 계속 정답을 받지 못해 다른 사람의 풀이도 참고했다.
문제를 조금 더 유심히 읽고 푸는 습관을 기르도록 하자..