boj2096 내려가기 (골드5) DP, online알고리즘, 슬라이딩 윈도우

문제 링크

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

2096번: 내려가기

 

 

---

내 풀이

이전에 들어온 배열(arr) 의 값을 a' b' c' 라고 하고, 이번에 들어온 입력을 a, b, c 라고 할 때

배열(arr)에는 a + max(a', b') 와 b + max(a', b', c') 그리고 c + max(b' + c') 가 저장된다. 

그 다음 입력값이 들어오면 배열(arr)과 비교해가며 불필요한 데이터는 저장하지 않고

딱 하나의 배열 arr 만 사용한다.

 

그 이유는 이 문제에서는 메모리 초과 문제가 발생한다. N이 최대 100,000개 이고, 한 줄에 3개씩 즉 300,000만개의 데이터가 들어오기 때문에 이 데이터를 하나의 배열에 저장하기만 해도 메모리 초과 에러가 뜨므로 이때 필요한 것이 online 알고리즘이다.

 

online 알고리즘이란

데이터가 들어오는 즉시 바로 처리함으로써 불필요한 데이터는 저장하지 않고 넘어가며 메모리를 적게 쓰는 방법이다.

 

동적계획법이란,

입력크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 문제를 해결하는 방법.

최종적으로 전체 문제를 해결하는 알고리즘이다.

상향식 접근법으로, 가장 최하위 해답을 구한 후 해당 결과값을 이용해서 상위 문제를 풀어가는 방식.

 

memorization 기법

프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술.

문제를 잘게 쪼갤 때 부분문제는 중복되어 재활용 된다.

예) 피보나치 수열 문제

 

# boj2096 내려가기
# 골드5

# 메모리 115176 KB
# 시간 196 ms

import sys

num = int(sys.stdin.readline())
min_arr = [0, 0, 0]
max_arr = [0, 0, 0]

for i in range(num):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    min_arr = [a + min(min_arr[:2]), b + min(min_arr), c + min(min_arr[1:])]
    max_arr = [a + max(max_arr[:2]), b + max(max_arr), c + max(max_arr[1:])]

print(max(max_arr), min(min_arr))