[파이썬] 백준 18111: 마인크래프트 (실버2)

[파이썬] 백준 18111: 마인크래프트 (실버2)

 

18111번: 마인크래프트

---

문제

---

풀이

0.방향성 생각

500x500x256까지 계산해서 모든 정보를 찾지 않고 적당하게 제한 조건을 걸어서 부분적으로 탐색할 수 있게 한다.

 

1. 입력 정보 받기

import sys
input = sys.stdin.readline

h,w,box = map(int,input().split())
height_info = {n : 0 for n in range(257)} # 각 블록이 몇 개 있는지 딕셔너리로 저장

arr = [] # 땅 정보
for i in range(h):
    temp = list(map(int,input().split()))
    arr.append(temp)
    for j in temp :
        height_info[j] += 1

height_info = list(height_info.items()) # (높이,개수) 리스트로 반환

 

2. 땅 높이에 따른 소모 시간 계산

time_list = []
for i in range(257):
    under = [(key,val) for key,val in height_info if key < i and val!=0]
    over = [(key,val) for key,val in height_info if key > i and val!=0]
    time,block = 0,0
    block += box
    
    for height,count in over:
        time += 2*(height-i)*count
        block += (height-i)*count
    for height,count in under:
        time += (i-height)*count
        block -= (i-height)*count

    if block < 0:
        break
    time_list.append(time)

i는 현재 땅 고르기를 할 높이이다.

i를 기준으로 낮은 블록 따로, 높은 블록 따로 (높이, 개수) 정보를 리스트에 할당한다.

땅고르기를 할 높이 i를 기준으로 높은 곳은 시간 소모가 2*(높이 차)*(땅 개수)이고 획득 블록은 (높이 차)*(땅 개수)이다. 

땅고르기를 할 높이 i를 기준으로 낮은 곳은 시간 소모가 (높이 차)*(땅 개수)이고 사용 블록은 (높이 차)*(땅 개수)이다.

 

만약에 블록을 다 사용해서 계산 시 블록 수가 음수가 된 경우 그 때부터는 그 높이 이상으로는 땅고르기가 불가능하므로 탈출한다.

 

3. 정답 출력

max_height_idx = [idx for idx,t in enumerate(time_list) if t == min(time_list)]
max_height = max(max_height_idx)
min_time = min(time_list)

print(min_time,max_height)

시간 소모가 가장 적은 것들의 인덱스들을 따온다.

그 인덱스 정보가 높이 정보랑 일치한다.

최소 시간은 time list에서 min으로 구한다.

---

전체코드

import sys
input = sys.stdin.readline

h,w,box = map(int,input().split())
height_info = {n : 0 for n in range(257)}

arr = []
for i in range(h):
    temp = list(map(int,input().split()))
    arr.append(temp)
    for j in temp :
        height_info[j] += 1

height_info = list(height_info.items())

time_list = []
for i in range(257):
    under = [(key,val) for key,val in height_info if key < i and val!=0]
    over = [(key,val) for key,val in height_info if key > i and val!=0]
    time,block = 0,0
    block += box
    
    for height,count in over:
        time += 2*(height-i)*count
        block += (height-i)*count
    for height,count in under:
        time += (i-height)*count
        block -= (i-height)*count

    if block < 0:
        break
    time_list.append(time)
    
max_height_idx = [idx for idx,t in enumerate(time_list) if t == min(time_list)]
max_height = max(max_height_idx)
min_time = min(time_list)

print(min_time,max_height)

 

코멘트

브루트포스는 항상 볼때마다 이렇게 풀어야 하나 생각이 듦