[18111] 마인크래프트

문제 이해

최대 500*500 사이즈이고 그 중에서 256 최대 높이니까 완전탐색 가능 
입력 받으중앙값 구함 안되네 애매하게 더 쌓아야할 수도 있으니까
시간이 적어야 하니까 타입별로 계산을 해야 하네
최소높이부터 최대높이까지 완전탐색을 해야겠다
면서 최저점이랑 최고점을 저장해 놔야겠다
최저 0이고 최고 1이면 0부터 1까지 기준을 0부터 시작
만약 다음 값이 기준보다 크면 차이값씩 증가
기준값보다 작으면 차이 * 2씩 감소

그럼 필요한 변수는
n, m, b
ground list
time = 0
block = 0

========================================
코드 계획

n, m, b
ground list
입력 받으면서
Min, Max 저장하기 
time = Max*n*m
block = 0
Min < Max 동안 반복하기
t = 0
b = 0
isAble = True
for i in range(n):
for j in range(m):
ground[i][j]가 Min보다 크면(기준값보다 크면)
t += (ground[i][j]  - Min ) * 2

작으면
만약 b가 있음
t += Min - ground[i][j]
없으면 쓸 블록이 없는거니까 불가능한 로직임
ifAble = False, break
if isAble != True : break
만약 answer값보다 time이 더 작고 isAble이면
time에 t 저장
block엔 Min 저장


3 4 0
1 0 0 0
0 1 0 0
0 0 0 1

6 0

 

초안

import sys

input = sys.stdin.readline

n, m, b = map(int, input().split())

ground = []

Max = 0

Min = 0

for i in range(n):

    t = list(map(int, (input().split())))

    ground.append(t)

    x = max(t)

    Max = max(x, Max)

    x = min(t)

    Min = min(x, Min)

time = Max*Max*n*m

block = 0

while Min <= Max:

    t = 0

    b_cnt = b

    isAble = True

    for i in range(n):

        for j in range(m):

            if ground[i][j] == Min: continue

            elif ground[i][j] > Min:

                    t += (ground[i][j] - Min) * 2

                    b_cnt += ground[i][j] - Min

            else:

                if Min - ground[i][j] >= b_cnt:

                    t += Min - ground[i][j]

                    b_cnt -= Min - ground[i][j]

                else:

                    isAble = False

                    break

        if isAble == False: break

    if t < time and isAble:

        time = t

        block = Min

    Min+=1

print(time, block)

 

결국 제미나이한테 물어봤다

1. 주요 오류 분석

1) 블록 계산 순서의 문제 현재 코드는 2중 for문을 돌면서 블록이 모자라면 즉시 isAble = False로 처리하고 중단합니다. 하지만 실제로는 높은 곳의 블록을 먼저 깎아서 인벤토리를 채운 뒤, 그 블록들로 낮은 곳을 메울 수 있습니다.

• 해결: 인벤토리에 있는 블록(b)에 깎아서 나온 블록을 모두 더한 총량이, 메워야 할 블록의 총량보다 크거나 같으면 작업이 가능합니다.

2) time 초기값 설정 time = Max*Max*n*m으로 설정하셨는데, 문제의 최대 범위를 고려하면 이 값이 충분히 크지 않을 수 있습니다. 보통 아주 큰 값(예: sys.maxsize)으로 설정하는 것이 안전합니다.

3) 최적의 높이(block) 갱신 조건 문제에서 "답이 여러 개 있다면 그중 높이가 가장 높은 것을 출력한다"고 명시되어 있습니다.

• 현재 코드: if t < time (시간이 같을 때 더 높은 높이로 갱신되지 않음)
• 수정 방향: if t <= time으로 하되, 높이를 낮은 곳부터 검사하므로 마지막에 갱신된 값이 가장 높은 높이가 됩니다.

맞네.. 바로 종료하면 안되는구나.. 

없앴는지 쌓았는지 블록을 이중반복으로 계산한 후에 한 번에 처리를 하는 방식으로 수정해야 한다

import sys

input = sys.stdin.readline

n, m, b = map(int, input().split())

ground = []

Max = 0

Min = 256

for i in range(n):

    t = list(map(int, (input().split())))

    ground.append(t)

    Max = max(Max, max(t))

    Min = min(Min, min(t))

   

time = sys.maxsize

block = 0

while Min <= Max:

    take_block = 0

    put_block = 0

    for i in range(n):

        for j in range(m):

            diff = ground[i][j] - Min

            if diff > 0:

                take_block += diff

            else:

                put_block -= diff

    if take_block + b >= put_block:

        t = take_block*2 + put_block

       

        if t <= time:

            time = t

            block = Min

    Min+=1

print(time, block)