BOJ 2096 - 내려가기

문제

백준 온라인 저지 - 2096번

풀이 과정

전형적인 DP 문제이지만 메모리 제한이 빡셉니다.
슬라이딩 윈도우 를 활용해서 memo 2차원 배열을 2 * 3 의 크기로 지정해서 값을 구하면 되는데
문제는 처음에 top-down 방식으로 접근했다가 board 배열의 크기를 줄일 방법이 없어서 계속 메모리 초과가 발생했습니다.
대신에 bottom-up 방식으로 변경하고 board 를 미리 입력 받는 것이 아니라
한 줄씩 입력 받아서 사용하는 것으로 변경하여 문제를 해결할 수 있었습니다.

코드

import sys

N = int(input())


def solution():
    min_memo = [[-1] * 3 for _ in range(2)]
    max_memo = [[-1] * 3 for _ in range(2)]
    board = list(map(int, sys.stdin.readline().split()))

    for i in range(3):
        min_memo[0][i] = board[i]
        max_memo[0][i] = board[i]

    for x in range(1, N):
        board = list(map(int, sys.stdin.readline().split()))

        min_memo[x % 2][0] = min(min_memo[(x - 1) % 2][0], min_memo[(x - 1) % 2][1]) + board[0]
        min_memo[x % 2][1] = min(min_memo[(x - 1) % 2][0], min_memo[(x - 1) % 2][1], min_memo[(x - 1) % 2][2]) + board[1]
        min_memo[x % 2][2] = min(min_memo[(x - 1) % 2][1], min_memo[(x - 1) % 2][2]) + board[2]

        max_memo[x % 2][0] = max(max_memo[(x - 1) % 2][0], max_memo[(x - 1) % 2][1]) + board[0]
        max_memo[x % 2][1] = max(max_memo[(x - 1) % 2][0], max_memo[(x - 1) % 2][1], max_memo[(x - 1) % 2][2]) + board[1]
        max_memo[x % 2][2] = max(max_memo[(x - 1) % 2][1], max_memo[(x - 1) % 2][2]) + board[2]

    max_value = max(max_memo[(N - 1) % 2])
    min_value = min(min_memo[(N - 1) % 2])

    return f"{max_value} {min_value}"


print(solution())