💻 백준 2096번: 내려가기

문제 소개 🧐

N x 3 크기의 숫자판에서, 첫 줄부터 마지막 줄까지 규칙에 맞게 내려오면서 얻는 점수의 최댓값과 최솟값을 구하는 문제이다. 다음 줄로 내려갈 때는 바로 아래 또는 대각선 아래로만 이동할 수 있다.

입력 📝

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 각 숫자는 0 이상 9 이하이다.

출력 📤

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 공백으로 구분하여 출력한다.

제한 ❌

  • 시간: 1초
  • 메모리: 4 MB

나의 풀이 과정 🌊

첫 번째 시도: 그리디

Idea: 각 행에서 다음으로 갈 수 있는 칸 중 가장 점수가 높거나/낮은 곳으로만 이동하는 그리디 전략을 사용했다. 하지만 현재의 최적 선택이 전체의 최적을 보장하지 않아 실패했다.

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
sadari = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
col_idx = [[0, 1], [0, 1, 2], [1, 2]]  # 이전 사다리 번호 따라 내려갈 수 있는 번호
score_col_list1 = [[float('inf'), 0]] * n
score_col_list2 = [[-1, 0]] * n

answer = [0,0]
score_col_list1[0] = [float('inf'), 1]
# 최소 찾기
for i in range(n):
    min_num, prev_col = score_col_list1[i]
    for col in col_idx[prev_col]:
        if sadari[i][col] < min_num:
            min_num = sadari[i][col]
            score_col_list1[i][1] = col

    answer[1] += min_num

# 최대
score_col_list2[0] = [-1, 1]
for i in range(n):
    max_num, prev_col = score_col_list2[i]
    for col in col_idx[prev_col]:
        if sadari[i][col] > max_num:
            max_num = sadari[i][col]
            score_col_list2[i][1] = col

    answer[0] += max_num

print(*answer)

Result: 실패 😭

두 번째 시도: 다익스트라

Idea: 모든 경로를 탐색해야 한다는 점에서 다익스트라를 떠올렸지만, N이 100,000까지 커질 수 있어 모든 경로를 저장하는 것은 4MB 메모리 제한을 초과했다.

import sys
import heapq
from collections import deque

n = int(sys.stdin.readline().rstrip())
sadari = deque(list(map(int, sys.stdin.readline().split())) for _ in range(n))
sadari.appendleft([0,0,0])
sadari = list(sadari)
near_c = [[0,1], [0,1,2], [1,2]]  # 다음에 갈 수 있는 곳

def search_sadair(sadari, n):
    pr_q = []
    start = [0, 0, [0,1,2]] # 점수, 행, 다음에 갈 수 있는 곳
    pr_q.append(start)
    min_list = [float('inf')] * (n+1)
    max_list = [-1] * (n+1)

    while pr_q:
        score, row, next_cols = heapq.heappop(pr_q)

        for c in next_cols:
            if row > n-1:
                break
            next_score = sadari[row+1][c] + score
            if next_score <= min_list[row+1]:
                min_list[row+1] = next_score
            if next_score > max_list[row+1]:
                max_list[row+1] = next_score
            tmp = [next_score, row+1, near_c[c]]
            heapq.heappush(pr_q, tmp)

    print(max_list[n], min_list[n])

search_sadair(sadari, n)

Result: 메모리 초과 😭

세 번째 시도: 공간 최적화 DP ✨

Idea: 4MB 메모리 제한을 통과하기 위해, 오직 이전 한 줄의 정보만 저장하는 공간 최적화 DP(슬라이딩 윈도우) 기법을 사용했다. 크기 3의 배열 두 개(max_li, min_li)만 유지하며, 각 줄을 읽을 때마다 이전 줄의 누적합을 바탕으로 현재 줄의 값을 갱신했다.

Code:

import sys

n = int(sys.stdin.readline().rstrip())

max_li = [0, 0, 0]
min_li = [0, 0, 0]

for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split())

    prev_max0, prev_max1, prev_max2 = max_li
    prev_min0, prev_min1, prev_min2 = min_li

    max_li[0] = max(prev_max0, prev_max1) + a
    max_li[1] = max(prev_max0, prev_max1, prev_max2) + b
    max_li[2] = max(prev_max1, prev_max2) + c

    min_li[0] = min(prev_min0, prev_min1) + a
    min_li[1] = min(prev_min0, prev_min1, prev_min2) + b
    min_li[2] = min(prev_min1, prev_min2) + c

print(max(max_li), min(min_li))

Result: 성공! ✅

배운 점 및 느낀 점 ✍️

  • 문제의 제약 조건, 특히 메모리 제한에 따라 공간복잡도 또한 고려해줘야 함을 깨달았다.

  • 슬라이딩 윈도우 DP: DP 테이블 전체를 유지할 필요 없이, 점화식에 필요한 최소한의 이전 상태만 저장하여 공간을 극적으로 아끼는 ‘슬라이딩 윈도우’ 기법을 체득했다.