[Python] 18111번 마인크래프트

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

18111번: 마인크래프트

---

22/08/28

 

 

이 문제 또한 클래스 2++ 문제 중 풀지 않은 문제가 있길래 풀어본 문제이다.

 

처음에 문제를 접근할 때, 분명 브루트 포스 문제이긴 한데 주어진 제한시간이 생각보다 여유롭지 않아서 마음속으로 어떻게 문제를 풀지 고민을 많이 했었다.

 

그래서 한 번 정도 시행 착오를 겪고 나서 푼 문제이다.

 

참고로 python3로는 시간이 너무 빡빡한 탓에 pypy로 제출했으니, python3로 제출할 생각이 있다면 다른 방법을 찾아보는 것이 좋을 것이다.

 

---

 

초반 문제 접근 방법:

 

 

일단 2차원 배열을 접근하는 것은 시간 면에서 많이 불리할 것이라고 생각했다.

 

때문에 이 마인크래프트 땅을 1차원 배열로 입력을 받자고 생각했다.

 

그리고 땅을 평평하게 만드는 기준을 세워야 되는데, 현재 입력받은 땅의 높이 중 제일 낮은 것부터 높은 것까지 반복하며 기준을 하나씩 세워서 확인하면 될 것이라고 생각했다.

 

이 부분에서 사실 구현을 잘 했었어야 됐는데, 문제를 잘 못 읽은 탓에 한번 틀리고 말았다.

 

나는 땅을 고르는 과정 중간에 한번이라도 인벤토리가 부족하여 부족한 땅을 못 채워 넣는 일이 생긴다면 멈추는 것으로 했었다.

 

근데 알고보니 그렇게 코드를 짜면 안 됐었고, 인벤토리가 부족한 것은 마지막에 한 번만 체크해주면 되는 것이었다.

 

---

 

나중 접근 방법:

 

 

이후 위에서 언급한 것처럼 인벤토리가 부족한 것은 마지막에 한 번만 체크를 해주었다.

 

이를 토대로 작성한 코드는 다음과 같다. 더보기를 누르면 확인할 수 있다.

# 18111번 마인크래프트
# 브루트포스, 구현
import sys
input = sys.stdin.readline  # 빠른 입력을 위한 코드

M, N, B = map(int, input().rstrip().split())
ground = []   # 땅을 1차원 배열로 입력받아서 접근을 빠르게 한다.
for _ in range(M):
    ground += list(map(int, input().rstrip().split()))
start = min(ground)
end = max(ground)
max_height = start   # 최소 시간으로 들 경우가 여러 개 있을 때, 최대 높이를 취하기 위한 변수
min_time = sys.maxsize  # 최소 시간을 구하기 위한 변수
for standard in range(start, end + 1):  # standard를 기준으로 모두 땅 높이를 standard에 맞춘다.
    inven = B  # 현재 인벤토리 상황
    time = 0  # 땅 작업 한 번 하는데 드는 시간
    for i in ground:
        k = i - standard
        if k > 0:   # 현재 땅 높이가 기준보다 높으면 깎아내린다.
            inven += k
            time += 2*k
        else:  # 같거나 낮으면 높인다.
            inven += k
            time += abs(k)
    if inven < 0:  # 땅 작업 한 번 했는데 인벤토리 부족하면 기준 바꿔서 다시한다.
        continue
    else:   # 정상적으로 땅 작업이 마쳐지면
        if time <= min_time:   # 최소 시간을 갱신해준다.
            max_height = standard
            min_time = time
print(min_time, max_height)