문제
https://www.acmicpc.net/problem/18111
풀이
- 블럭의 최대 높이 256, N과 M의 값 <= 500
- 1초 이하로 계산 가능하기 때문에 브루트 포스 가능 - 높이, 행, 렬 모두 탐색하기 위해 삼중 for문
1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.- 1번 작업 2초, 2번 작업 1초
- 각 층을 순회하여 (i,j) 좌표 별로 층을 초과하는 블럭, 부족한 블럭 계산
- 초과하는 블럭 + 인벤토리에 있는 블럭이 부족한 블럭 보다 많을 경우 조건문 실행(블럭을 제거하여 얻은 블럭과 인벤토리에 있는 블럭이 설치해야 하는 블럭보다 많아야 되기 때문)
- 0층부터 256층까지 순회하기 때문에 정답이 여러개일 경우 가장 높은 층을 출력하는 것도 만족
코드
import sys
input = sys.stdin.readline
n,m,b = map(int,input().split())
land = [list(map(int,input().split())) for _ in range(n)]
res = sys.maxsize # 작업 시간
idx = 0 # 가장 높은 층
for floor in range(257): # 0층부터 차례대로 순회
excess, lack = 0, 0 # 초과하는 블럭, 부족한 블럭
for i in range(n):
for j in range(m):
if land[i][j] >= floor: # (i,j)가 층수보다 높을 경우
excess += land[i][j] - floor # 초과분에 값 추가
else: # 낮을 경우
lack += floor - land[i][j] # 부족분에 값 추가
if excess + b >= lack: # 초과하는 블럭 + 인벤토리에 있는 블럭 >= 부족한 블럭일 경우
if lack + (excess * 2) <= res: # 블럭을 설치한 시간(1초) + 블럭을 제거하는 시간(2초)가 기존 시간보다 작을 경우
res = lack + (excess * 2) # 설치 시간 + 제거 시간
idx = floor # 층수 업데이트
print(res, idx)