백준 2096 < 내려가기 > Python

📍문제 링크

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

2096번: 내려가기

 

📍알고리즘 분류

- 다이나믹 프로그래밍

- 슬라이딩 윈도우

 

📍문제 풀이

세 수가 일렬로 쭉 내려오는 수열이 있다. 내려올 때, 직선, 대각선으로 내려올 수 있다고 할 때

최댓값과 최솟값을 구하라

 

/*
1번 라인	1 2 3
2번 라인	4 5 6
3번 라인	4 9 0


1
1 2 3
일 때 각 라인에서 가능한 최대 최소

	1	2	3
최대	1	2	3
최소	1	2	3


2
1 2 3
4 5 6
일 때 각 라인에서 가능한 최대 최소

최대	6(4 + 2)	8(5 + 3)	9(6 + 3)
최소	5(4 + 1)	6(5 + 1)	8(6 + 2)

점화식을 세우면
s11 s12 s13
s21 s22 s23 일때

dp(2) = [
[ s21 + max(s11, s12), s22 + max(s11, s12, s13), s23 + max(s12, s13) ]
[ s21 + min(s11, s12), s22 + min(s11, s12, s13), s23 + min(s12, s13) ]
]


이 성립한다

*/

 

JavaScript로는 메모리 초과로 인해 풀 수 없는 것으로 보인다..

 

📍코드

import sys

N = int(input())
a, b, c = map(int, input().split())
d = a
e = b
f = c

for i in range(N - 1):
    x, y, z = map(int, sys.stdin.readline().rstrip().split())
    A = x + max(a, b)
    B = y + max(a, b, c)
    C = z + max(b, c)
    D = x + min(d, e)
    E = y + min(d, e, f)
    F = z + min(e, f)
    a = A
    b = B
    c = C
    d = D
    e = E
    f = F

print(max(a, b, c), min(d, e, f))

 

- large A, B ... 등을 사용하는 이유

그냥 a, b, c 를 사용하면 a, b, c가 최신화 할때마다 다음 값에 간섭하여 형태가 왜곡됨

 

📍리뷰

- sliding window는 알고리즘이 아니라 테크닉으로, DP 에서 배열 대신 변수를 사용하여 메모리를 아끼는 것을 지칭하기도 한다

(토글링이라고도 한다)