문제 링크

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

문제 설명

• 3 x n board에서 내려가면서 최댓값, 최솟값 구하기

풀이

접근

• 처음에 간단한 DP라고 생각했다

난관1

• 그대로 구현하니 메모리 초과가 났다
• 살짝 멘붕올뻔 했지만 마음을 가다듬고 생각해봤다
• 처음에 n x 3이 아니라 n x 1 크기로 만들어볼까 했지만 이전 경로도 알아야 되기 때문에 그건 안 된다는걸 알았다

해결

• DP 리스트를 생각해보니 바로 이전 값들만 참조하면 되기 때문에 굳이 n개만큼 만들 필요가 없었다
• 2 x 3을 두 개 만들어서 계산해주고 위치 바꿔주는 식으로 했다

난관2

• 근데 마지막에 100프로에서 또 오답나와서 혼란스러웠다

해결

• 질문들을 보다가 n이 1일 경우에 오답이란걸 알았다

코드

import sys
read = sys.stdin.readline
n = int(read())
board = [list(map(int, read().split())) for _ in range(n)]
dp_max = [board[0], [0,0,0]]
dp_min = [board[0], [0,0,0]]

for y in range(1, n):

    dp_max[1][0] = max(dp_max[0][0], dp_max[0][1]) + board[y][0]
    dp_max[1][1] = max(dp_max[0]) + board[y][1]
    dp_max[1][2] = max(dp_max[0][1], dp_max[0][2]) + board[y][2]
    dp_max[0] = dp_max[1][:]
    
    dp_min[1][0] = min(dp_min[0][0], dp_min[0][1]) + board[y][0]
    dp_min[1][1] = min(dp_min[0]) + board[y][1]
    dp_min[1][2] = min(dp_min[0][1], dp_min[0][2]) + board[y][2]
    dp_min[0] = dp_min[1][:]
    
print(max(dp_max[0]), min(dp_min[0]))