18111

날짜 : 2022. 12. 19

사용 언어 : python

 

문제

 

 

코드

import sys

n, m, b = map(int, sys.stdin.readline().split())  # 행, 열, 인벤토리
field = []
ans = int(1e9)
height = 0

for i in range(n):
    t = list(map(int, sys.stdin.readline().split()))
    field.append(t)

for h in range(257):
    over = 0  # 기존 높이가 더 큰 경우(블록을 뺌)
    low = 0  # 기존 높이다 작은 경우(블록을 더함)
    for i in range(n):
        for j in range(m):
            if field[i][j] < h:  # 블록을 넣어야 하는 경우
                low += (h - field[i][j])  # 인벤토리에서 뺄 블록의 개수
            else:  # 블록을 빼는 경우
                over += (field[i][j] - h)  # 인벤토리에 넣을 블록 
    inven = over + b  # 반영
    if inven < low: continue  # 인벤토리가 마이너스(구현 불가능) -> pass
    cnt = 2 * over + low  # 시간 갱신
    if cnt <= ans:  # 갱신(시간이 더 짧은 경우)
        ans = cnt
        height = h

print(ans, height)

 

 

풀이

- 주석 참고

 

 

알게된 점

- 브루트포스 문제라고는 했는데 0부터 256까지 체크하지 못한 점, 인벤토리에서 뺀 개수와 넣은 개수를 모두 구한 다음 합산하지 않은 것이 아마 계속 오답이 나타난 이유라고 생각한다.

- 그때그때 필터링하는 것도 좋겠지만 위와같은 유형의 문제인 경우에는 시간초과가 발생하지 않을 것이기 때문에 전부 구한 다음에 하나씩 출력하는 것도 좋지 않을까 싶다.

 

 

참고 사이트

-