[실버2]백준 18111번(마인크래프트) - 코테공부 27일차(2025.02.18)

문제유형

빈도수 배열 활용

풀이 방법 도출 과정

1. 마크에서 땅 고르기 작업을 해야한다. 

2. 좌표 (i, j)에서 블록을 제거하거나 추가해야 한다.

- 블록을 제거하는 데는 2초가 걸리며

- 블록을 추가하는 데는 1초가 걸린다. 

3. 밤에는 무서운 몬스터가 나오기 때문에, 가능한 한 빨리 작업을 끝내야 한다.

4. 땅 고르기 작업에 걸리는 최소 시간과 그 경우의 땅 높이를 출력해야 한다.

 

5. 이 문제는 빈도수 배열을 이용한 브루트 포스를 사용해서 풀어야 한다.

6. 가장 먼저 빈도수 배열을 생성한다.

7. 모든 가능한 목표 높이에 대한 시뮬레이션을 한다.

8. 인벤토리 조건 확인 및 최적 해를 선택한다. 

시간 복잡도

시간 복잡도는 모두 O(n x m)이다. 하지만 n과 m을 500에서 257로 줄여 시간복잡도를 절반으로 낮추었다.

코드 및 간단설명

빈도수 배열과 브루트 포스를 활용한 코드이다. 

import sys
input = sys.stdin.readline

n, m, b = map(int, input().split())
freq = [0] * 257
for _ in range(n):
    for height in map(int, input().split()):
        freq[height] += 1

# 높이별 블록 개수 누적합과 높이*개수 누적합을 미리 계산 (0~i 까지)
prefix = [0] * 257      # 각 높이까지의 블록 개수 합
prefix_sum = [0] * 257  # 각 높이까지의 (높이 * 블록 개수) 합

prefix[0] = freq[0]
prefix_sum[0] = 0  # 0 * freq[0]
for i in range(1, 257):
    prefix[i] = prefix[i-1] + freq[i]
    prefix_sum[i] = prefix_sum[i-1] + i * freq[i]

ans_time = float('inf')
ans_height = 0

# 모든 가능한 목표 높이를 순회 (0~256)
for target in range(257):
    # target 보다 높은 곳 (target+1 ~ 256)의 블록들을 제거할 경우
    # 제거 블록 수 = (해당 구간의 총 블록 높이 합) - target * (해당 구간의 블록 개수)
    remove = (prefix_sum[256] - prefix_sum[target]) - target * (prefix[256] - prefix[target])
    
    # target 보다 낮은 곳 (0 ~ target-1)의 블록들을 채울 경우
    # 필요한 블록 수 = target * (해당 구간의 블록 개수) - (해당 구간의 총 블록 높이 합)
    add = target * prefix[target-1] - prefix_sum[target-1] if target > 0 else 0

    # 인벤토리와 제거한 블록들로 채울 수 없는 경우는 건너뛰기
    if b + remove < add:
        continue

    time = remove * 2 + add  # 제거: 2초, 추가: 1초
    # 최소 시간 우선, 같다면 더 높은 높이 선택
    if time < ans_time or (time == ans_time and target > ans_height):
        ans_time = time
        ans_height = target

print(ans_time, ans_height)