[백준/Python] 2096. 내려가기

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

 

📌  문제 접근

원룡이가 한줄씩 내려가면서 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제이다.

DP를 이용해서 풀면 된다고 생각했다. 

 

🔍 첫 번째 풀이 (실패)

처음에는 이중 for문 + 2차원 DP 테이블을 사용했다.

N = int(input()) 
arr = [[0] + list(map(int, input().split())) + [0] for _ in range(N)] 

mxdp = [[0] * (N + 2) for _ in range(N)] 
mxdp[0] = arr[0] 
for i in range(1, N): 
	for j in range(1, N + 1): 
    	mxdp[i][j] = max(mxdp[i - 1][j - 1], mxdp[i - 1][j], mxdp[i - 1][j + 1]) + arr[i][j] 

print(max(mxdp[N - 1]))

 

그 다음 제약조건을 다시 확인했는데

1 ≤ N ≤ 100,000

이었다 .. 

DP 테이블을 N × N 크기로 만들면 메모리가 터질 것 같았다 !

🔍 두 번째 풀이 (성공)

문제를 다시 읽어보니, N개의 줄에 숫자가 3개씩 주어진다.
즉, 매 줄마다 필요한 값은 단 3개뿐이었다.

따라서, 굳이 전체 DP 테이블을 저장할 필요가 없고
이전 줄의 3개 값만 저장해두면 충분하다.

N = int(input())
first = list(map(int, input().split()))

mx = first[:]
mn = first[:]

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

    prev_mx = mx[:]
    mx[0] = max(prev_mx[0], prev_mx[1]) + a
    mx[1] = max(prev_mx[0], prev_mx[1], prev_mx[2]) + b
    mx[2] = max(prev_mx[1], prev_mx[2]) + c

    prev_mn = mn[:]
    mn[0] = min(prev_mn[0], prev_mn[1]) + a
    mn[1] = min(prev_mn[0], prev_mn[1], prev_mn[2]) + b
    mn[2] = min(prev_mn[1], prev_mn[2]) + c

print(max(mx), min(mn))

 

3개의 값만 저장하여 공간 복잡도를 O(3)으로 줄일 수 있었다.