주어진 크기의 마인크래프트 지형과 인벤토리의 사용가능한 블럭 수에 대해 일정한 높이로 만드는 최소 시간과 그 높이를 구하는 문제입니다. 마인크래프트 맵을 그대로 배열에 옮겨넣은 후 높이마다 각 칸마다의 행동을 찾고, 그 코스트(사용하는 블럭 수, 시간)의 합계를 구합니다. 블럭 사용의 경우 주어진 블럭보다 많으면 해당 높이는 불가능한 높이이고, 시간에 대해서는 가장 적은 시간, 시간이 같다면 가장 높은 높이를 저장하여 반복문이 끝나고 출력합니다.
이 문제는 단순 브루트 포스라기에는 시간이 좀 부족합니다. 만약 브루트 포스였다면 난이도가 Silver III일리는 없겠죠…? 따라서 시간을 단축하는 것이 필요한데, 여러 방법이 있습니다. 첫 번째는 높이 범위의 축소입니다. 마인크래프트에 존재할 수 있는 높이는 [0, 256]인데, 입력받은 맵의 최소 높이보다 작거나 최대 높이보다 큰 높이값은 답이 될 수 없습니다. 행동하는 데에 시간이 너무 오래 걸리기 때문이죠. 따라서 높이를 순회할 때 맵의 최소 높이에서 최대 높이까지만 해주어도 됩니다. 두 번째는 맵 저장 방식의 변경입니다. C/C++과 같이 빠른 언어는 이 과정이 필요없지만, Python과 같은 상대적으로 느린 언어는 이 과정이 필요할 수도 있습니다. 하려는 행동의 특성 상 맵의 인접 칸에는 전혀 영향을 받지 않습니다. 따라서 맵을 2차원 배열로 저장하는 것이 아닌 어떤 높이에 몇 개의 칸이 존재하는가만 저장해도 됩니다. 이 경우 반복문 안에서 맵을 순회하는 과정이 짧아지고, 코스트를 구하는 과정도 짧아집니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-07 13:34:38 |