[BOJ] Q2096 내려가기

[BOJ] Q2096 내려가기

Question

Language: Python

Difficulty: Gold 4

해당 문제는 정수 삼각형 문제q1932와 비슷한 방식으로 풀면 된다.

단, 메모리 용량을 최소화 시켜야한다. 그래서 위의 정수 삼각형 처럼, N*3의 직사각형을 그대로 memoization 하면 안된다. 메모리를 최소화 하기 위해, 최소,최대에 대하여, 이전 행, 현재 행만 이용해서 이들을 갱신하는 방향으로 진행하면된다.

현재 행에 대한 조사를 끝마치면 현재행이 이전행이 되고, 다음 행이 현재행이 된다.

Solution

from math import inf
def solution():
    prev_min_board=graph[0]
    prev_max_board=graph[0]

    for i in range(1,n):
        min_board=[inf]*3
        min_board[0]=min(prev_min_board[0]+graph[i][0],prev_min_board[1]+graph[i][0])
        min_board[1]=min(prev_min_board[0]+graph[i][1],prev_min_board[1]+graph[i][1],prev_min_board[2]+graph[i][1])
        min_board[2]=min(prev_min_board[1]+graph[i][2],prev_min_board[2]+graph[i][2])
        
        max_board=[0]*3
        max_board[0]=max(prev_max_board[0]+graph[i][0],prev_max_board[1]+graph[i][0])
        max_board[1]=max(prev_max_board[0]+graph[i][1],prev_max_board[1]+graph[i][1],prev_max_board[2]+graph[i][1])
        max_board[2]=max(prev_max_board[1]+graph[i][2],prev_max_board[2]+graph[i][2])

        prev_min_board=min_board
        prev_max_board=max_board
    

    print(max(prev_max_board),min(prev_min_board))

if __name__ == "__main__":
    n=int(input())
    graph=[list(map(int,input().split())) for _ in range(n)]
    
    solution()