문제

2096 - 내려가기

접근

DP 문제이다.

한 줄씩 내려오며 만난 숫자를 더하여 최대값, 최소값을 만드는 문제이다.

이 때 원하는 곳으로 내려갈 수 있는게 아니라, 이전 상태의 영향을 받게된다.

이전 위치에서 좌,우로 최대 한칸밖에 움직이지 못한다.

즉, 이전에 (i, 0)번 위치에 있었다면 (i+1, 0), (i+1, 1)까지, (i, 1)번 위치에 있었다면 (i+1, 0), (i+1, 1), (i+1, 2) 이런 식이다.

가로는 3칸밖에 되지 않으므로 처음에는 n*3의 배열을 최대값, 최소값에 대해 두개 만들어서 진행했다.

DP 구성은 DP(i, j) = (i, j)의 수 + DP(i-1, x) 의 최대값(이 때 j-1 <= x <= j+1)

x가 0, 2일 때 범위가 배열을 벗어나는 문제 때문에 배열을 5칸으로 두고 양 옆에 빈 공간을 두는 식으로 하였다.

DP 자체는 간단한 문제이므로 그렇게 어렵지 않았지만 메모리 제한을 아주 많이 두었다.

통째로 배열을 만들어서 진행하면 메모리 초과가 뜰 수 밖에 없다.

이 문제에서 결국 중요한 것은 가장 마지막 줄에서 최대값 혹은 최소값이 어떻게 나왔는지이다.

그리고 이를 구하기 위해서는 그 전 줄만 보면 된다.

즉, DP 식 자체가 현재 줄인 i와 이전 줄인 i-1만 알면 구할 수 있는 것이다.

따라서 입력을 받는 동시에 DP연산을 수행했으며, DP자체도 2*5배열로 구성하고 한줄씩 로테이션시켜주면서 진행했다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import sys
input = sys.stdin.readline

n = int(input())

maxDP = [[0] * 5 for _ in range(2)]
minDP = [[987654321] * 5 for _ in range(2)]
for i in range(1,4):
    minDP[0][i] = 0

now, before = 1, 0
for i in range(n):
    board = list(map(int, input().split(' ')))
    for j in range(1,4):
        maxDP[now][j] = max(maxDP[before][j-1:j+2]) + board[j-1]
        minDP[now][j] = min(minDP[before][j-1:j+2]) + board[j-1]
    now, before = before, now

print(max(maxDP[n%2][1:4]), min(minDP[n%2][1:4]))