[BOJ] 백준 18111 마인크래프트 (Swift)

문제

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

풀이

이 문제를 처음 봤을 때, 어떻게 풀어야 할 지 생각을 좀 해봤다.
결론으로는 가능한 높이를 모두 만들어보고, 최소한의 수를 구하는 방법을 택해야겠다고 생각했다.

원래 이런 문제들을 풀 때, 사람이라면 어떻게 계산할 까 생각을 해봤는데..
뭐 전부 1이고 하나만 0이면 그냥 한 개 가방에 있는거 꺼내면 되겠다 이런 생각이 들었었다.
그런데 제각각 다른 수일 때, 인간이 이걸 어떻게 계산할까 생각을 해보다가
모든 경우의 수를 확인해봐야겠다고 생각이 들었다.

이 문제에서는 최소 0에서 255까지의 높이까지 쌓을 수 있다고 했으므로, 모두 균일하게 해당 높이를 맞춰보는 식으로 구하고자 했다.
n,m이 500이고 높이가 255이므로 255 * 500 * 500은 1초안에 충분히 구할 수 있겠다고 생각이 들었고 코드를 짜봤다.

먼저 높이를 0부터 시작을 해, 모든 블록을 해당 높이에 맞춰주는 방식으로 구하였다.

1. 블록의 높이가 맞춰주려고 하는 높이보다 크다면, 블록을 빼서 가방에 넣어준다 (블록 1개당 1초)
2. 블록의 높이가 맞춰주려고 하는 높이보다 작거나 같다면, 가방에서 블록을 꺼내서 쌓아주자 (블록 1개당 2초)

모든 블록에 대해 이 행위를 하고, 가방에 남은 블록의 수가 0보다 작지 않다면 해당 높이를 만들 수는 있는 것이다.
이제 여기서 얼마만큼의 시간이 걸렸는지 계산을 해주고, 가장 적게 걸리는 시간을 찾자. 255까지 반복하면 된다.

소스코드

후기

구현력과 완전탐색이 필요한 문제였다. 나름 재밌었던 문제