이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 처음에는 주어진 2차원 배열을 만든 뒤에 내려가며 최대와 최소에 해당하는 수들을 각각 저장하여 해결해야겠다고 생각을 했다. 하지만 그렇게 되면 입력값이 너무 많아져 메모리 제한을 초과한다는 사실을 알게 되었다. 그래서 각 줄을 입력 받을 때 마다 누적값의 최대와 최소를 구하여 저장해놓는 방식으로 구현하였다.

• n을 입력받는다.
• 각 줄에 해당하는 가장 큰 결과 값과 가장 작은 결과값을 저장할 maxDP, minDP 배열을 선언한다.
• maxDP, minDP를 구하기 위해 계산값을 임시로 저장해 놓을 maxTemp, minTemp 배열을 선언한다.
• 0부터 n-1까지 반복하는 i에 대한 for문을 돌린다.
• num1,num2,num3을 입력받는다. 이는 입력되는 2차원 배열의 한 줄을 의미하는 것이다.
• 0부터 2까지 반복하는 j에 대한 for문을 돌린다.
  -> j가 0일때는 num1을, 1일때는 num2를, 2일때는 num3을 선택한 상황으로 이는 왼쪽, 가운데, 오른쪽 수를 의미한다.
  -> j에 해당하는 num과 이전의 maxDP, minDP를 이용하여 j에 해당하는 maxTemp, minTemp를 구한다.
• 0부터 2까지 반복하는 j에 대한 for문을 돌린다.
  -> maxTemp, minTemp의 값을 maxDP, minDP에 저장한다.
• 반복문이 모두 끝나면 maxDP의 최댓값과 minDP의 최솟값을 출력한다.

Code

n=int(input())
maxDP=[0]*3
minDP=[0]*3
maxTemp=[0]*3
minTemp=[0]*3
for i in range(n):
    num1,num2,num3 = map(int, input().split())
    for j in range(3):
        if j==0:
            maxTemp[j]=num1+max(maxDP[j], maxDP[j+1])
            minTemp[j]=num1+min(minDP[j], minDP[j+1])
        elif j==1:
            maxTemp[j]=num2+max(maxDP[j-1], maxDP[j], maxDP[j+1])
            minTemp[j]=num2+min(minDP[j-1], minDP[j], minDP[j+1])
        else:
            maxTemp[j]=num3+max(maxDP[j-1], maxDP[j])
            minTemp[j]=num3+min(minDP[j-1], minDP[j])
    for j in range(3):
        maxDP[j]=maxTemp[j]
        minDP[j]=minTemp[j]
print(max(maxDP), min(minDP))