마인크래프트

18111번: 마인크래프트

 

나의 풀이

import sys
input = sys.stdin.readline

n, m, inb = map(int, input().rstrip().split())

ct, deep = float('inf'), 0
map_list = []
for _ in range(n):
    map_list.append(list(map(int, input().rstrip().split())))

for i in range(257): # 땅 높이
    use_block = 0
    delete_block = 0
    
    for a in range(n):
        for b in range(m):
            if map_list[a][b] > i:
                delete_block += (map_list[a][b] - i)
            else:
                use_block += (i - map_list[a][b])
    if use_block > (delete_block+inb):
        continue
    
    now_ct = (delete_block*2) + use_block
    if now_ct <= ct:
        ct, deep = now_ct, i
print(f"{ct} {deep}")

 

시간 복잡도

for a in range(n) : 모든 맵을 탐색하며 블록 갯수 확인 ( 이차형 시간 복잡도 )
        for b in range(m) :
            내부 루프 : 상수 시간
해당 알고리즘 시간복잡도는 이차형 시간 복잡도 ( O(n**2) )