문제

• 
• 시간 제한: 1초
• 메모리 제한: 4MB

Problem Analysis

N 줄의 k 번째 칸으로 끝나는 최댓값은, N-1 줄의 k-1, k, k+1 칸으로 끝나는 최대값과 조합하여 얻을 수 있다. 이렇게 재귀적으로 쪼개서 풀 수가 있는데, sub-problems이 반복된다. 따라서 Dynamic Programming으로 풀 수 있다. 또한, 주어진 메모리가 상당히 작기 때문에 최적화가 중요하다.

Algorithm

위의 그림처럼, recursive call을 이용하면 Top-Down 방식으로 풀 수 있다. 이를 기반으로, N = 1 일 때부터 계산하도록 하면, Bottom-Up 방식으로 iterative 하게 개선할 수 있다. 이때, N 행의 dp을 계산하기 위해서 N-1 행만 필요하다. 따라서, 두 줄의 dp를 가지고 최종 값을 계산할 수 있다.

Data Structure

• 2x3 Array, 최대와 최소를 계산하기 위한 dp 저장용 두 개

결과

Other

이처럼,
1) dp의 사이즈를 조절하면서, 메모리 사용량을 조절할 수 있다.
2) Bottom-Up 방식으로 개선하여, Top-Down 방식에서 발생하는 recursive call로 인한 메모리 사용을 줄일 수 있다.