[백준/18111] 마인크래프트

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

18111번: 마인크래프트

[알고리즘]

1) 완전 탐색 시간 복잡도

500 * 500 * 256 = 64,000,000 때문에 min, max를 정해서 사용했는데 생각해보니 하나의 land에 0과 256이 같이 들어있으면 min_land = 0, max_land = 256이 되어서 방지할 수 없다. 그래서 3중 for문으로 완전 탐색을 하게 되면 시간 초과다.

 

2) 이를 해결하기 위해 이차원리스트(land)에서 같은 높이를 가지는 블럭들을 하나의 list에 저장해준다. 그러면 같은 값이 있는 블럭은 중복으로 확인할 필요가 없기 때문에, 3중 for문 없이 모든 블럭의 높이를 같게 해주는 계산을 수행할 수 있다.

[시초코드]

from sys import stdin
input = stdin.readline
n,m,b = map(int, input().split())
land = [list(map(int, input().split())) for _ in range(n)]

min_land = min(map(min, land))
max_land = max(map(max, land))

ans = 1e9
for x in range(min_land, max_land+1) : 
    # 인벤토리에서 가져와야 할 최소/최댓값
    min_num, max_num = 0, 0
    for i in range(n) : 
        for j in range(m) :
            if land[i][j] < x : 
                min_num += (x-land[i][j])
            else:
                max_num += (land[i][j]-x)
                
    # 남아있는 inventory 
    # max_num은 블록을 가지런히 하고도 남으니까 inven에 채워주기
    inventory = b + max_num
    
    if inventory < min_num : continue
    
    t = 2 * max_num + min_num
    # 최소 시간, 가장 높은 높이
    # 어차피 오름차순 탐색이기 때문에, tall은 신경쓸 필요 x    
    if t <= ans : 
        ans = t
        tall = x
        
print(ans, tall)

[정답 코드]

 

[알게된 점]

• int 범위 내에서 무한(INF)값 이용하기
  • 1e9 = 1*10**9 = 1,000,000,000,
  • 2e9 = 2*10**9 = 2,000,000,000
• 이중리스트에서 원소의 최소/최댓값 구하는 방법
  • min(map(min, list))
  • max(map(max, list))
• 파이썬의 시간 복잡도 : 5초에 1억

---

Reference

https://land-turtler.tistory.com/82

[18111] 마인크래프트(python)

https://thflgg133.tistory.com/88

[Baekjoon/Python] 18111번: 마인크래프트 - 효과는 굉장했다!