백준 2096 내려가기

과정

• DP
• 메모리가 4MB로 제한되어 있다.
  • 모든 경우를 포함하여 2차원 배열을 만들면 메모리 초과가 발생한다.
  • 리스트 크기를 최소한으로 제한해야 했다.
• 따라서 현재 값만을 가지고 있는 리스트만을 사용해서, 각 칸마다 최대값, 최소값으로 변경하는 방식으로 진행했다.

메모리 초과가 발생한 코드

N = int(input())

max_dp = []
min_dp = []
for _ in range(N):
    lst = list(map(int, input().split()))
    max_dp.append(list(lst))
    min_dp.append(list(lst))

for y in range(N):
    for x in range(N):
        if y == 0:
            continue
        if x == 0:
            max_dp[y][x] += max(max_dp[y - 1][x], max_dp[y - 1][x + 1])
            min_dp[y][x] += min(min_dp[y - 1][x], min_dp[y - 1][x + 1])
        elif x == N - 1:
            max_dp[y][x] += max(max_dp[y - 1][x - 1], max_dp[y - 1][x])
            min_dp[y][x] += min(min_dp[y - 1][x - 1], min_dp[y - 1][x])
        else:
            max_dp[y][x] += max(max_dp[y - 1][x - 1], max_dp[y - 1][x], max_dp[y - 1][x + 1])
            min_dp[y][x] += min(min_dp[y - 1][x - 1], min_dp[y - 1][x], min_dp[y - 1][x + 1])


print(max(max_dp[-1]), min(min_dp[-1]))

통과한 코드

N = int(input())

lst = list(map(int, input().split()))
max_dp = list(lst)
min_dp = list(lst)

for _ in range(1, N):
    a, b, c = map(int, input().split())

    x = max(max_dp[0], max_dp[1]) + a
    y = max(max_dp[0], max_dp[1], max_dp[2]) + b
    z = max(max_dp[1], max_dp[2]) + c

    max_dp[0] = x
    max_dp[1] = y
    max_dp[2] = z

    x = min(min_dp[0], min_dp[1]) + a
    y = min(min_dp[0], min_dp[1], min_dp[2]) + b
    z = min(min_dp[1], min_dp[2]) + c

    min_dp[0] = x
    min_dp[1] = y
    min_dp[2] = z


print(max(max_dp), min(min_dp))