백준 실버2 18111. 마인크래프트 (python)

마인크래프트

 

인벤토리에 블록이 하나 있기 때문에, 맨 오른쪽 아래에 블록을 하나 채우면 된다.

풀이

처음 푼 풀이는 아래와 같은 풀이로 3중 for문이였다.
시간초과가 났다...
pypy3로 하니 통과는 하는데... 흐음...

import sys
N, M, B = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
min_value = sys.maxsize
index = 0

# 땅의 높이는 256보다 작거나 같은 자연수 또는 0이므로 0부터 순회
# 이 땅 높이로 만드려는 거임
for height in range(257):
    # 초과, 부족 블록 갯수
    excess, lack = 0, 0
    # 행 순회
    for i in range(N):
        # 열 순회
        for j in range(M):
            # 현재 확인중인 높이보다 땅높이가 높으면
            if board[i][j] > height :
                excess += board[i][j] - height
            # 현재 확인중인 높이보다 땅높이가 높지 않으면
            else : 
                lack += height - board[i][j]
    # 초과량 + 인벤토리가 부족과 같거나 크면
    if excess + B >= lack :
        # 땅다지는 시간이 min_value보다 작으면 실행
        if (excess * 2) + lack <= min_value:
            min_value = (excess * 2) + lack
            index = height
print(min_value, index)

위의 방법이 너무 오래 걸리니 다른 방법을 찾아보았다.
미리 땅의 갯수를 파악하고, 함수를 포함해 이중 for문의 방식이다.

1. 땅의 높이를 입력
2. 만드려고 하는 땅의 높이를 for문으로 실행
3. for문안에서 함수를 실행
4. 해당 함수안에서 만드려는 땅의 높이를 만들기 위해 필요한 블록과 시간을 계산하고 이를 반환
5. 완료 후 최소 시간과 그 중 가장 높은 땅의 높이를 출력

def solution(height):
    # 추가해야할 블록 갯수
    need = 0
    # 파내야할 블록 갯수
    unnecessary = 0
    # 0~256까지 확인
    for i in range(257):
        # 현재 높이의 갯수, 만드려는 높이와의 차
        current_nums, diff = height_nums[i], i-height
        # 현재 높이의 갯수가 0이면 넘어가기
        if current_nums == 0:
            continue
        # 높이 차이가 0 미만이면, 추가할 블록 갯수
        if diff < 0:
            need += (-diff) * current_nums
        # 높이 차이가 0이상이면, 파내야할 블록 갯수 추가
        else:
            unnecessary += diff * current_nums
    
    # 인벤토리 블록과 파낸 블록의 양이 추가해야할 블록갯수 이상이면? 시간구해야지
    if (unnecessary+ B) >= need:
        # 작업1번(땅파기) 시간 1초와 작업2번(채워넣기) 시간 2초임을 생각하고 계산
        time = need + unnecessary * 2
        return time
    # 그게 안되면?
    else:
        return sys.maxsize

import sys
N, M, B = map(int, sys.stdin.readline().split())
# 높이별 땅의 갯수
height_nums = [0]* 257
# height_nums에 입력값 기록
for i in range(N):
    for j in list(map(int,input().split())):
        height_nums[j] += 1 
# 최소 시간
min_times = sys.maxsize -1
# 최소 시간의 높이 변수
answer_height = 0

# 0~256 까지의 땅의 높이로 만드는데 걸리는 시간 구하기
for height in range(257):
    time_value = solution(height)
    # 땅고르기 최소시간 그리고 땅 높이
    # 답이 여러개가 있다면, 그 중 땅의 높이가 가장 높은 것을 출력해야하므로 같아도 확인
    if time_value <= min_times:
        min_times = time_value
        answer_height = height
print(min_times, answer_height)

문제에서 제한사항이 출력과 입력 부분에 있어서 몇 번씩이나 틀렸다. 같은 최소 시간이면 높이가 더 높게 하라고 한 것을 못보고 코드를 입력해서 답을 찾는데 더 오래 걸렸다.

문제를 더 꼼꼼하게 확인해야겠다.