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

1. 문제

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

18111번: 마인크래프트

2. 구현 과정

- 완전 탐색으로 처음 풀었더니, 시간 초과가 났다. 500*500*256이 파이썬에선 1초가 넘어가는 걸 처음 알았다.. C++만 풀어왔던 나에겐 다소 충격(저 크기가 초과가 난다고?)이었고, 앞으로는 주의해서 풀어야 겠다.

 

- 완전 탐색에 실패해서 그 다음 이분 탐색으로도 고민을 해 보았지만, 답을 구하려는게 최소-최대 높이가 아닌 최소 소요시간 이라는 점에서 정확한 기준점?을 찾기 어려웠다. 결국 완전탐색으로 풀되, 적어도 2중 for문 내에서 해결 가능하도록 풀이가 필요했다.

 

- 처음 완전 탐색에서는 3중 for문 ( N, M, H)가 필요했다. 2차원 배열을 다 돌면서 각 배열값의 높이를 비교하는 거였는데,그렇게 하면 시간초과가 나니까 다른 방법으로 접근을 해야 한다. 어차피 풀이를 위해 필요한 건 "어떤 좌표에서 소요시간이 얼마나 걸렸냐" 가 아니라 "총 소요시간이 얼마나 걸렸냐"이기 때문에, 2차원 배열에 각 높이값들의 개수를 저장하는 list를 만들면 된다. 즉, 높이값이 i인 곳이 몇 개 있는지를 저장하는 list를 생성하면 굳이 3중 for문을 돌지 않고 한번에 계산이 가능하다.

 

- 또한 모든 높이값 범위(0~256)로 평탄화 하는데 걸리는 시간을 측정할 필요가 없었다. 블록의 최소 높이 ~ (모든 블록 개수의 합) // M*N의 범위까지 가능하므로, 해당 범위만큼 for문을 돌리면 된다.

 

3. 실수한 부분 & 처음 안 부분

1) for문 내에 상수를 쓰기보단, 변수로 넣는 습관을 들이자 (대문자로 선언하기)

2) 2차원 배열의 최소값을 구하는 법 : min_value = min([ min(row) for row in board ]) 

3) 파이썬에서의 시간 복잡도 : 1초에 약 2000만 ( 5초에 1억)

4) 문제에서 같은 시간이 걸린다면, 더 높은 높이값으로 출력하래서 시간이 같을 때 높이값을 또 비교하려 했는데, for문에선 높이값을 오름차순으로 비교하므로 비교할 필요가 없었다. ( 쓸데 없는 코드 줄이는 습관)

5) 이 문제에선 for문 내에서 가능한 경우의 수가 무조건 3가지 경우 중 하나였다. ( h < i, h == i, h > i ) 이 경우에 굳이 h == i 일때 continue문은 안적어도 될 듯 하다 ( 코드 줄이기)

 

4. 코드

 

1. 정답 코드

#입력받기
MAX_HEIGHT = 256
MIN_HEIGHT = 0
N, M, B = map(int, input().split())
board = [ list(map(int, input().split())) for _ in range(N)]
height_cnt = [0 for _ in range(MAX_HEIGHT + 1)]
answer_cost = 100000001
answer_height = 0
sum_height = B 

#각 높이의 개수를 저장하는 리스트 입력받기 
for row in board:
    for val in row:
        height_cnt[val] += 1
        sum_height += val
     
#가능한 높이값들을 저장
min_h = min([ min(row) for row in board ])
max_h = sum_height // (M * N)

#각 높이를 평탄화 하는데 걸리는 시간 탐색미
for h in range(min_h, max_h+1):
    cost = 0
    usable_blocks = B
    for i in range(MIN_HEIGHT, MAX_HEIGHT+1 ):
        if h < i:
            cost += height_cnt[i] * abs(h - i) * 2
            usable_blocks += height_cnt[i] * abs(h - i)
        else:
            cost += height_cnt[i] * abs(h - i)
            usable_blocks -= height_cnt[i] * abs(h - i)
            
    if cost <= answer_cost and usable_blocks >= 0:
        answer_cost = cost
        answer_height = h

print(answer_cost, answer_height)

2. 시간초과 난 코드

#입력받기
N, M, B = map(int, input().split())
board = [ 0 for _ in range(N) ]
second = 10000000
height = 0
sum_height = 0 #전체 높이의 합

for i in range(N):
	board[i] = list(map(int,input().split()))
	sum_height += sum(board[i])

#가능한 높이값들을 저장
height_set = set()
min_height = 0
max_height = sum_height // (M * N)

for i in range(max_height+1): #첨엔 min~max로 했었음 
	height_set.add(i)

height_list = list(height_set) #중복제거를 위해 set으로 입력받은 후 ,list로 변경

#가능한 높이값들로 평탄화 시키기 위해 걸리는 시간 측정
for h in height_list:
	basket = B #인벤토리 내 값 개수
	sec = 0 

	for i in range(N):
		for j in range(M):
			if board[i][j] == h:
				continue
			elif board[i][j] > h:
				basket += 1
				sec +=2
			else:
				basket -= 1
				sec += 1
	
	#인벤토리 내 개수가 음수개면 불가능한 경우로 판단
	if basket < 0:
		continue
	elif sec < second:
		second = sec
		height = h

print(second,height)