문제 보기 · Level 4 · Summer/Winter Coding(~2018) · 정답률 22% · 푼 사람 965명 (2026-09-30 기준)1

문제

N×N 땅의 칸마다 블록이 쌓여 있다. 모든 칸의 높이를 같게 만든다. 블록 하나를 더하는 데 P, 빼는 데 Q의 비용이 든다. 필요한 비용의 최솟값을 돌려준다.

  • 1 ≤ N ≤ 300
  • 칸의 높이 0 ~ 10억, 1 ≤ P, Q ≤ 100

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 정렬과 정렬 기준: 높이를 정렬하면 “목표보다 낮은 칸”과 “높은 칸”이 앞뒤로 나뉜다.
  • 누적 합과 차분 배열: 앞쪽 칸들의 높이 합을 누적 합으로 두면, 목표 높이마다 비용을 \(O(1)\)에 구한다.
  • 볼록 함수와 볼록 최적화: 목표 높이를 t, 칸 높이를 h라 하면 칸 하나의 비용 P × max(t − h, 0) + Q × max(h − t, 0)은 한 번 꺾인 볼록 함수다. 볼록 함수의 합도 볼록이라, 전체 비용은 줄다가 늘기만 하고 다시 줄지 않는다.
1단계 · 작은 예로 손으로 풀기

높이 [1, 2, 2, 3], P = 3, Q = 2

  • 목표 1: 빼기 1 + 1 + 2 = 4개 → 8
  • 목표 2: 더하기 1개(3), 빼기 1개(2) → 5
  • 목표 3: 더하기 2 + 1 + 1 = 4개 → 12

답은 5다. 목표를 1씩 올리면 비용이 줄다가 늘어난다. 가장 낮은 곳은 늘 어느 칸의 높이와 같은 곳에서 나온다.

2단계 · 가장 단순한 방법과 그 속도

목표 높이를 0부터 10억까지 모두 해 보면 10억 × 칸 9만 개로 어림없다. 목표 후보를 “지금 있는 높이”로 줄여도, 후보마다 칸을 모두 보면 9만 × 9만 = 81억 번이다.

3단계 · 핵심 아이디어
  • 후보는 지금 있는 높이뿐: 목표 t를 1 올리면, t 이하인 칸 k개는 블록이 1개씩 더 필요하고(+P씩), t보다 높은 칸 n − k개는 1개씩 덜 빼도 된다(−Q씩). 비용 변화는 kP − (n − k)Q다. k는 t가 칸 높이를 지날 때만 바뀌니, 두 높이 사이에서는 비용이 한 방향으로만 변한다. 그래서 가장 낮은 비용은 어느 칸의 높이에서 나온다.
  • 가장 싼 높이는 분위수: 비용 변화 kP − (n − k)Q는 k/n이 Q/(P + Q) 이상일 때부터 0 이상이다. 그래서 답은 그 높이 이하인 칸이 처음으로 전체의 Q/(P + Q) 이상이 되는 높이, 곧 높이들의 Q/(P + Q) 분위수(최근접 순위 방식)다. P = Q면 중앙값이다.
  • 누적 합으로 한 번에: 높이를 정렬한 h와 누적 합 S를 둔다(S[i]는 앞 i칸의 합). 목표 t보다 낮은 칸이 k개면
    • 더할 블록: t × k − S[k]
    • 뺄 블록: (S[n] − S[k]) − t × (n − k)
  • k는 bisect_left(h, t)로 구한다.
4단계 · 코드 흐름
  1. 모든 칸의 높이를 한 줄로 모아 정렬하고, 누적 합 S를 만든다.
  2. 서로 다른 높이 t마다: k = t보다 낮은 칸 수, 더할 블록 × P + 뺄 블록 × Q를 계산한다.
  3. 가장 작은 비용을 돌려준다.
5단계 · 파이썬 코드 
from bisect import bisect_left

def solution(land, P, Q):
    h = sorted(x for row in land for x in row)
    n = len(h)
    S = [0]
    for x in h:
        S.append(S[-1] + x)                 # S[i]: 낮은 쪽 i칸의 높이 합
    best = None
    for i, t in enumerate(h):               # 목표 높이 후보
        if i > 0 and h[i - 1] == t:
            continue                        # 같은 높이는 한 번만
        k = bisect_left(h, t)               # t보다 낮은 칸 수
        add = t * k - S[k]
        remove = (S[n] - S[k]) - t * (n - k)
        cost = add * P + remove * Q
        if best is None or cost < best:
            best = cost
    return best
  • sorted(x for row in land for x in row): 2차원 땅을 한 줄로 펴서 정렬한다.
  • 정렬된 목록에서 같은 높이의 첫 번째 칸은 i 자신이라 bisect_left(h, t)는 i와 같다. 읽기 쉽게 bisect로 썼다.
6단계 · 실행 추적

land = [[4, 4, 3], [3, 2, 2], [2, 1, 0]], P = 5, Q = 3. 정렬하면 [0, 1, 2, 2, 2, 3, 3, 4, 4]이고, 높이 합 S[9] = 21이다.

목표 t 낮은 칸 k 더할 블록 뺄 블록 비용
0 0 0 21 63
1 1 1 13 44
2 2 2 × 2 − 1 = 3 (21 − 1) − 2 × 7 = 6 33
3 5 8 2 46
4 7 15 0 75

가장 작은 비용은 33이다. 문제 설명의 “높이 3이면 46”과도 맞는다.

7단계 · 복잡도와 흔한 실수

칸 수 M = N²에 정렬 \(O(M \log M)\), 후보마다 \(O(\log M)\)이다. 300×300에서 재 보니 0.1초가 안 걸렸다.

  • 목표 높이를 0 ~ 최대 높이까지 모두 돌려 시간 초과가 난다.
  • 평균 높이나 중앙값 하나만 답으로 쓴다. P와 Q가 다르면 가장 좋은 높이가 한쪽으로 치우친다.
  • 누적 합 없이 후보마다 모든 칸을 다시 더한다.
검증: 문제의 예시 2개를 통과했고, 6단계 표의 비용을 코드로 계산해 맞췄다. 무작위 입력 2,000개(높이 0 ~ 12)에서 “최소 높이부터 최대 높이까지 모든 정수 높이를 해 보는” 풀이와 결과가 같았다. 300×300, 높이 10억의 시간도 쟀다 — 19_pg12984_p1.py

  1. 프로그래머스 스쿨, “지형 편집” (https://school.programmers.co.kr/learn/courses/30/lessons/12984), 2026-09-30 조회. ↩