[BOJ] 2096 내려가기

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

3열 짜리 배열이 있는데 아래 행으로 가면서 합치는데 +-1의 열에 있는 숫자와 합칠 수 있다. 이렇게 합쳐서 최대, 최소값을 구하라는 문제이다.
DP라는 것을 알고나서 원래 하던대로 DP 배열을 선언하고 기록하면서 처리했다.

n = int(input())

table = [list(map(int, input().split())) for _ in range(n)]

minDp = [[10, 10, 10] for _ in range(n)]
maxDp = [[-1, -1, -1] for _ in range(n)]

minDp[0] = table[0]
maxDp[0] = table[0]

# minDp[n][0] = min(minDp[n-1][0] + table[n][0], minDp[n-1][1] + table[n][0])

for i in range(1, n):
  minDp[i][0] = min(minDp[i-1][:2]) + table[i][0]
  minDp[i][1] = min(minDp[i-1]) + table[i][1]
  minDp[i][2] = min(minDp[i-1][1:]) + table[i][2]
  
  maxDp[i][0] = max(maxDp[i-1][:2]) + table[i][0]
  maxDp[i][1] = max(maxDp[i-1]) + table[i][1]
  maxDp[i][2] = max(maxDp[i-1][1:]) + table[i][2]
  
print(max(maxDp[-1]), min(minDp[-1]))

이번에는 메모리 초과가 났다.
아무래도 10만 X 3 크기의 배열을 3개나 만들어서 그런가 싶어서 minDp, maxDp는 2칸짜리 배열로 줄이기로 했다.

n = int(input())

table = [list(map(int, input().split())) for _ in range(n)]

minDp = [[10, 10, 10] for _ in range(2)]
maxDp = [[-1, -1, -1] for _ in range(2)]

minDp[0] = table[0].copy()
maxDp[0] = table[0].copy()

for i in range(1, n):
  minDp[i%2][0] = min(minDp[abs(i%2-1)][:2]) + table[i][0]
  minDp[i%2][1] = min(minDp[abs(i%2-1)]) + table[i][1]
  minDp[i%2][2] = min(minDp[abs(i%2-1)][1:]) + table[i][2]
  
  maxDp[i%2][0] = max(maxDp[abs(i%2-1)][:2]) + table[i][0]
  maxDp[i%2][1] = max(maxDp[abs(i%2-1)]) + table[i][1]
  maxDp[i%2][2] = max(maxDp[abs(i%2-1)][1:]) + table[i][2]
  
print(max(maxDp[(n-1)%2]), min(minDp[(n-1)%2]))

index가 홀, 짝에 따라서 새롭게 업데이트 되는 칸이 달라지게 했다. 마지막 index는 n의 길이가 홀수인지 짝수인지에 따라서 달라지게 했다.
n이 홀수라면 마지막 업데이트 되는 위치는 0번자리, 짝수라면 1번자리이기에 n-1해서 2로 나눈 나머지로 구했다.
그러나 이렇게 해도 메모리 초과가 발생했다.

그래서 입력되는 배열도 없애보기로 했다.

n = int(input())

minDp = [[10, 10, 10] for _ in range(2)]
maxDp = [[-1, -1, -1] for _ in range(2)]

for i in range(n):
  row = list(map(int, input().split()))
  
  minDp[i%2] = row.copy()
  maxDp[i%2] = row.copy()
  if i > 0:
    minDp[i%2][0] = min(minDp[abs(i%2-1)][:2]) + row[0]
    minDp[i%2][1] = min(minDp[abs(i%2-1)]) + row[1]
    minDp[i%2][2] = min(minDp[abs(i%2-1)][1:]) + row[2]
    
    maxDp[i%2][0] = max(maxDp[abs(i%2-1)][:2]) + row[0]
    maxDp[i%2][1] = max(maxDp[abs(i%2-1)]) + row[1]
    maxDp[i%2][2] = max(maxDp[abs(i%2-1)][1:]) + row[2]
  
print(max(maxDp[(n-1)%2]), min(minDp[(n-1)%2]))

최초에 입력받을 때 이후에는 같은 로직이 실행되도록 했다.