2096번 내려가기 G4

N줄에 각 줄마다 0~9 인 숫자가 3개씩 적혀있고

첫 줄부터 시작해서 마지막 줄까지 내려가면 끝나는 놀이이다.

한 줄씩 내려갈 때 마다 숫자를 하나씩 골라서 내려가는데,

다음 줄로 내려갈 때는 고른 위치에 인접한 곳으로만 내려갈 수 있다.
바로 아래 칸이나 아래 칸에 붙어있는 칸으로만 갈 수 있다는 말이다.

이때 얻을 수 있는 최대 점수와 최소 점수를 구해야한다.

당연히 dp 문제이고 비슷한 문제를 풀어봐서 별로 고민하지 않았다.

근데 그냥 하던대로 하고나서 제출하기 전에 보니 메모리 제한이 4MB였고

그냥 그대로 내면 무조건 메모리 초과가 뜨는 코드였다.

그래서 숫자를 3개씩 입력 받으면서 dp 테이블도 함께 초기화 시킬 수 있도록 코드를 변경했다.

입력과 dp 테이블이 차지하는 공간은 n이 몇이어도 항상 똑같다.

내용은 단순하다.
dp[0]에는 최대값을, dp[1]에는 최소값을 저장했다.
한 줄 내려갈 때마다 이전 줄에서 최대값 혹은 최소값을 가져오면서 함께 더해주면
해당 칸으로 내려올 수 있는 최대, 최소 값이 된다.

3번째 줄 가운데 칸이라면
2번째 줄 왼쪽 위, 바로 위, 오른쪽 위 중에서 가장 큰 숫자를 가지고 와서 3번째 줄 가운데 숫자와 더하면
3번째 줄 가운데 칸으로 올 수 있는 최대 값이다.
물론 이때 2번째 줄에서 선택된 최대 값 역시 2번째 줄까지 올 수 있는 최대 값이다.

코드가 별로 이쁘지는 않은데 그냥 뒀다.

from sys import stdin

n = int(stdin.readline())
dp = [[0 for i in range(3)] for j in range(2)]
for i in range(n):
    nums = list(map(int, stdin.readline().rstrip().split()))
    
    left_max = max(dp[0][0], dp[0][1])
    right_max = max(dp[0][1], dp[0][2])
    
    left_min = min(dp[1][0], dp[1][1])
    right_min = min(dp[1][1], dp[1][2])
    
    dp[0][0] = nums[0] + left_max
    dp[0][1] = nums[1] + max(left_max, right_max)
    dp[0][2] = nums[2] + right_max
    
    dp[1][0] = nums[0] + left_min
    dp[1][1] = nums[1] + min(left_min, right_min)
    dp[1][2] = nums[2] + right_min

print(str(max(dp[0]))+' '+str(min(dp[1])))

아래는 메모리 조건을 보지 않고 작성한 코드

from sys import stdin

n = int(stdin.readline())
nums = [list(map(int, stdin.readline().split())) for i in range(n)]

dp = [[[0 for i in range(3)] for j in range(n)] for k in range(2)]

dp[0][0][0] = nums[0][0]
dp[0][0][1] = nums[0][1]
dp[0][0][2] = nums[0][2]

dp[1][0][0] = nums[0][0]
dp[1][0][1] = nums[0][1]
dp[1][0][2] = nums[0][2]

for i in range(1, n):
    left_max = max(dp[0][i-1][0], dp[0][i-1][1])
    right_max = max(dp[0][i-1][1], dp[0][i-1][2])
    dp[0][i][0] = nums[i][0] + left_max
    dp[0][i][1] = nums[i][1] + max(left_max, right_max)
    dp[0][i][2] = nums[i][2] + right_max
    
    left_min = min(dp[1][i-1][0], dp[1][i-1][1])
    right_min = min(dp[1][i-1][1], dp[1][i-1][2])
    dp[1][i][0] = nums[i][0] + left_min
    dp[1][i][1] = nums[i][1] + min(left_min, right_min)
    dp[1][i][2] = nums[i][2] + right_min
    
print(max(dp[0][-1]), end=' ')
print(min(dp[1][-1]))