[알고리즘/구현] 18111번 : 마인크래프트 - python

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

 

 

---

• 문제
• 소요시간: 45분

---

• 설계하기(접근방법) 

1. 입력받기

 땅을 입력받는다

 

땅의 모양은 상관 없기 때문에 편의를 위해 한 배열에 담아도 된다

 

2. 구현하기

문제의 핵심은 브루트 포스로 풀어야 하지만,

모든 경우의 수를 테스트할 필요가 없다는 것이다.

 

가장 낮은 땅의 높이보다 낮은 높이는

검사할 필요가 없다.

 

그렇다면 가장 높은 높이는 어떻게 정하는가?

 

가능한 가장 높은 높이는

(전체 블록의 수 + 주어진 인벤토리의 블록 수) // 전체 땅 넓이이다

 

이보다 더 블록을 가져올 수는 없다.

 

가장 낮은 높이와 높은 높이가 정해졌다. 

시간은 어떻게 구할까?

입력받기에서 말했던 내용에 이어서

목표한 땅의 높이를 h라고 할 때,

우리는 땅과 h와의 차이만 구하면 된다.

블록을 어떤 좌표에서 가져오는지는 중요하지 않기 때문이다.

둘의 차이의 부호에 따라 *2 혹은 그대로 시간에 더한다.

 

최대 높이가 정해지면

인벤토리에 블록이 몇 개 있는지는 중요하지 않다.

 

가장 높은 높이보다 낮은 높이에서는

인벤토리에 블록이 있는 여부와 관계없이

항상 블록이 남기 때문이다

 

인벤토리가 비어있고

5 4 3

5 4 3

5 4 2

라는 땅에는 평균에 의해 가장 높은 높이는 3이다

5와 4라는 땅을 3으로 만들면 9개의 잉여 블록이 생기고

나머지에 배분해도 남는다

 

이보다 낮은 높이일수록 잉여 블록의 개수는 더 늘어난다

목표 높이가 낮은만큼 총 사용되는 블록의 개수가 줄어가기 때문이다

 

 

3. 출력하기

최대 높이의 최소 시간을 출력한다

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n, m ,b = map(int, input().split())
mine = []

for _ in range(n):
    ground =list(map(int, input().split()))
    for i in ground:
        mine.append(i)

maxi = (sum(mine) + b) // (n*m)
min_time = 10e9
ground_h = 0

# i = 목표, h = 현재
for i in range(maxi , min(mine) - 1, -1):
    time = 0
    for h in mine:
        if h - i >= 0:
            time += (h - i) * 2
        else:
            time += (i - h)
    if time < min_time :
        min_time = time
        ground_h = i
print(min_time, ground_h)

---

• 얻어갈 부분

1. 최소 시간을 구하는 경우, 가장 편리하게 브루트포스를 떠올리자. 시간복잡도가 넉넉하면 시도해보자