[Python]백준 18111 마인크래프트 (feat. gpt o1보다 조금 똑똑..한건가..?)

 

https://www.acmicpc.net/problem/18111

 

문제분석

블럭이 지형을 이루고 있을때, 최단 시간 내에 평탄화하는 방법. 그때의 최대 높이를 구하시오.

해결과정

처음에는 높이별로 블럭을 누적시키려고 하였다(예를들어, 높이 3 블럭은 리스트[1]=1 리스트[2]=1 리스트[3]=1로 저장함으로써, 리스트[n]에는 n에 존재하는 블럭 수 를 저장하려고 하였다.

from sys import stdin
def input():
    return stdin.readline().rstrip()
N,M,B=map(int,input().split())
ground_extent=N*M

# height[n]은, 높이 n에 존재하는 블럭 
height=[0]*256
ground_block_sum=0
max_height=0 # 블럭이 쌓인 최고 높이
for i in range(N):
    temp_arr=list(map(int,input().split()))
    for j in temp_arr:
        for k in range(j+1):
            height[k]+=1
        max_height=max(max_height,j)
    ground_block_sum+=sum(temp_arr)
height=height[:max_height+1]# max_height인덱스까지 가져옴
height[0]=0

max_height=(ground_block_sum+B)//ground_extent


# 높이를 0으로 맞추는데 드는 리소스, 높이마다 전부 계산(높이의 범위는 max_height)
resources=[]    # [i,result] i 층 만드는데 드는 총 리소스
for i in range(max_height+1):
    present_block=sum(height[0:i+1])  # 이미 존재하는 블럭
    removed_block=sum(height[i+1:])   # 삭제해야 하는 블럭
    result=0
    if i==0:
        result=2*removed_block # 0은 존재하는 블럭이 없기 때문임
    else:
        result=i*(ground_extent)-present_block+2*removed_block # 삭제 총 소요 시간
    resources.append([result, i])

result=min(resources,key=lambda x:(x[0]))

print(*result)

결과는 잘 출력해주나, 시간 초과가 뜬다는 단점이 있다.

GPT한테 시간을 줄일 수 있는 방법을 물어보았다

블럭의 끝만 저장하고, 끝이 존재하는 위치-목표높이 를 계산하면 채워야 하는 블럭 수/없에야 하는 블럭 수를 알 수 있음.

당연히 GPT가 틀릴 줄 알고, 그냥 넣어봤는데...

import sys
input = sys.stdin.readline

N, M, B = map(int, input().split())
freq = [0]*257  # 혹시나 최대 높이가 256일 수 있으므로 257까지

max_height = 0
min_height = 256

for _ in range(N):
    row = list(map(int, input().split()))
    for h in row:
        freq[h] += 1
        if h > max_height:
            max_height = h
        if h < min_height:
            min_height = h

# 결과 변수: (최소 시간, 그 때의 높이)
answer_time = float('inf')
answer_height = 0

# 문제에서 이론적으로 가능한 높이 범위:
# "0부터 (가장 높은 칸 + B를 쌓았을 때) 중 일부" 혹은
# "입력값 중 최대 높이(max_height) ~ 재고 포함" 정도를 검사
# 여기서는 0~max_height+? 까지 일일이 확인해도 256 이하면 상수 시간.

for H in range(max_height + 1):
    remove_time = 0
    build_time = 0
    removed_blocks = 0
    needed_blocks = 0

    for i in range(max_height + 1):  # 혹은 257까지
        if freq[i]:
            if i > H:
                remove_time += 2 * (i - H) * freq[i]
                removed_blocks += (i - H) * freq[i]
            elif i < H:
                build_time += 1 * (H - i) * freq[i]
                needed_blocks += (H - i) * freq[i]

    # 필요한 블록을 인벤토리 + 제거블록으로 충당 가능한지 확인
    if removed_blocks + B >= needed_blocks:
        total_time = remove_time + build_time
        if total_time < answer_time:
            answer_time = total_time
            answer_height = H
        elif total_time == answer_time and H > answer_height:
            # 시간이 같으면 더 높은 높이를 택한다는 문제 조건
            answer_height = H

print(answer_time, answer_height)

그냥 맞춰버리네...?

o1이 무섭다...완벽하게 정답을 맞추더라...

그러나, 코드를 보는데 이상한 점이 있었다.

• 왜 제거 블럭을 생각하지? 시간만 생각하면 되는 것 아닌가?
• 높이의 상한은 어차피 총 블럭 수//면적 일텐데, 왜 최고 높이까지 고려하는 것인가?

아무리 생각해도 이 부분은 필요 없어 보여, 이를 제거하고 코드를 수정해보았다.

from sys import stdin
def input():
    return stdin.readline().rstrip()
N,M,B=map(int,input().split())
ground_extent=N*M

# height[n]은, 높이 n에 존재하는 블럭. 높이가 7인 좌표에는, height[7]에만 1이 찍히고, 6,5..에는 0
height=[0]*257
ground_block_sum=0
max_height=0 # 블럭이 쌓인 최고 높이
for i in range(N):
    temp_arr=list(map(int,input().split()))
    for j in temp_arr:
        height[j]+=1
        max_height=max(max_height,j)
    ground_block_sum+=sum(temp_arr)

result_max_height=(ground_block_sum+B)//ground_extent #결과로 나올 수 있는 최고 높이
answer_time=float('inf')
answer_height=0

for i in range(result_max_height+1): #계산할 높이들
    remove_time=0
    build_time=0
    for j in range(max_height+1): #j 높이에서, 블럭을 더하고 뺄 때의 소모 시간을 계산해야 
        if height[j]:
            if i>j:
                build_time+=(i-j)*height[j]
            elif j>i:
                remove_time+=2*(j-i)*height[j]
    total_time=build_time+remove_time
    if answer_time>total_time:
        answer_time=total_time
        answer_height=i
    elif answer_time==total_time:
        if answer_height<i:
            answer_height=i
print(answer_time, answer_height)

 

다행이 맞았?다..o1보다 나은건지 못한건지..