BaekJoon 18111번 : 마인크래프트 (python)

BaekJoon 18111번 : 마인크래프트 (S2 23.742%)

무려 7번 틀리고, 2번 시간 초과가 난 다음에 10번째로 맞은 문제이다.
그래도 이 모든 과정이 1시간안에 이루어진 과정이라 다행이다.

제일 처음 풀이법은 3중 for문을 이용해서 답을 구하는 과정이었는데 물론 이 방법엔 오류도 있었고 구현이 된다고 해도 시간초과로 틀리게 된다.
결국 이 문제는 미리 구할 수 있는 값들은 미리 구해서 한꺼번에 풀이를 하면 되는 문제이다.

• 그래프를 탐색하며 0부터 256까지 높이별로 count를 미리미리 해줌으로써 n*m 시간복잡도를 미리 계산한다.
• 높이 0부터 256까지의 for문을 크게 씌워주고 그 안에 작은 for문을 통해 주어진 높이 i를 만들기 위한 미리 저장한 높이 j를 비교하면서 시간과 인벤토리 개수를 계산해준다.
• 만약 계산한 높이 i에서 인벤토리에 블럭이 0개 미만이라면 해당 높이는 계산할 수 없는 높이로 탐색 대상에 append하지 않는다.
• 모아놓은 i들중에 시간이 가장 짧고 높이가 가장 높은 순서로 result를 sort하여 result[0]에 해당 답을 위치해 놓고 출력한다.

import sys
input = sys.stdin.readline

N, M, B = map(int,input().split())
graph = list()

for _ in range(N) :
    s = list(map(int,input().split()))
    graph.extend(s)

height = [0] * 257
for i in graph:
    height[i] += 1

result = list()
for i in range(257) :
    inven = B
    time = 0
    for j in range(257) :
        if j < i :
            inven -= (i-j)*height[j]
            time += (i-j)*height[j]
        elif j > i :
            inven += (j-i)*height[j]
            time += (j-i)*height[j]*2
    
    if inven >= 0 :
        result.append((time, i))

result.sort(key = lambda x: (x[0],-x[1]))
print(result[0][0], result[0][1])