[파이썬, Python] 백준 2096: 내려가기

문제

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

2096번: 내려가기

코드

n = int(input())

board = list(map(int, input().split()))

top = board
bottom = board

for _ in range(n - 1):
    board = list(map(int, input().split()))

    top = [board[0] + max(top[0], top[1]), board[1] + max(top), board[2] + max(top[1], top[2])]
    bottom = [board[0] + min(bottom[0], bottom[1]), board[1] + min(bottom), board[2] + min(bottom[1], bottom[2])]

print(max(top), min(bottom))

설명

점화식을 세우는 것은 크게 문제가 없었는데 메모리 제한이 작아서 어려운 문제였다.

우선 갈 수 있는 방향의 점수를 구해주는 방법은 다음과 같다.

1번 칸의 경우 윗 줄의 1번, 2번 중에 제일 큰 수와 현재 줄의 1번 칸의 합
2번 칸의 경우 윗 줄의 1번, 2번, 3번 중에 제일 큰 수와 현재 줄의 2번 칸의 합
3번 칸의 경우 윗 줄의 2번, 3번 중에 제일 큰 수와 현재 줄의 3번 칸의 합

이런 식으로 점화식은 간단하게 세울 수 있다.

하지만 주어진 메모리가 굉장히 작기 때문에 이를 해결해야 하는데
이는 변수를 재활용하면서 해결이 가능하다.

입력 값을 한 번에 받지 않고 각 줄마다 받아주며, 이때의 최대, 최소 값을 계산해 준다.
이러한 방식으로 사용했던 공간에 재할당하여 메모리의 사용을 줄인다.