[백준] 2096번 : 내려가기

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

해당 문제는 캐싱으로 문제를 해결 하였습니다.

캐싱을 할때에 필요한 배열은 temp 변수와 현재 최대값 ,최소값을 저장하는 current 변수를 선언 하였습니다.

정수 삼각형 문제처럼 문제를 해결하면 됩니다. 현재 값은 이전에 값중에서 최소값 혹은 최대값을을 선택 한뒤 자기자신을 더하면 됩니다.

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]))