[백준] 2096번 : 내려가기

2096번: 내려가기

해당 문제는 다이나믹 프로그래밍 문제로 메모리 제한이 4MB이다 따라서 2차원 배열이 아닌 1차원 배열로 문제를 해결해야한다.

current 변수에 최대값과 최소값이 저장될 값이고 temp로 받아서 한 단계씩 내려갈때마다 정수삼각형을 구하는 문제처럼 최소값과 최대값을 갱신하면서 내려가면 된다.

N = int(input())

current = [[0,0] for _ in range(3)] # maxValue, minValue

for _ in range(N):
    a,b,c = map(int, input().split())
    # 최대값 구하기
    temp = [0 for _ in range(3)]
    temp[0] = a + max(current[0][0], current[1][0]) # 첫번째 수
    temp[1] = b + max(current[0][0], current[1][0], current[2][0]) # 두번째 수
    temp[2] = c + max(current[1][0], current[2][0]) # 세번째 수
    
    for i in range(len(temp)):
        current[i][0] = temp[i]
    
    # 최소갑 구하기
    temp[0] = a + min(current[0][1], current[1][1]) # 첫번째 수
    temp[1] = b + min(current[0][1], current[1][1], current[2][1]) # 두번째 수
    temp[2] = c + min(current[1][1], current[2][1]) # 세번째 수
    
    for i in range(len(temp)):
        current[i][1] = temp[i]
    
print(max(current[0][0], current[1][0], current[2][0]), end=' ')
print(min(current[0][1], current[1][1], current[2][1]))