3×n 직사각형의 각 칸에 점수가 있을 때, 아래 또는 대각선으로 계속 내려가면서 얻을 수 있는 최대 점수와 최소 점수를 출력하는 문제입니다. 이 문제는 ① 1149 - RGB거리와 상당히 유사한 문제로, DP를 이용해서 풀 수 있습니다. 하지만 문제의 조건을 보면 메모리 제한이 4MB로 상당히 작은 것을 알 수 있습니다. 만약 직사각형의 높이가 100000이라면 각 점수를 모두 저장하는 것이 1200000 바이트로 약 1.2MB입니다. 혹시 모르기 때문에 이렇게 큰 배열을 사용하는 것은 별로라고 생각합니다.
이 때 생각할 수 있는 방법이 한 줄 입력과 DP값 업데이트를 반복하는 것입니다. 예를 들어, 100번째 줄을 탐색하고 있는데 1번째 줄의 점수값을 저장할 필요가 없습니다. 마찬가지로 100번째 줄에서 1번째 줄에 썼던 DP 값 또한 필요가 없습니다. 바로 직전 줄을 탐색해서 얻은 DP값만 필요합니다. 따라서 입력용 크기 3짜리 배열과 DP용 크기 2×3짜리 배열 2개(최대, 최소)만 있으면 한 줄 입력받고, DP값을 계산하고, 를 반복하여 정답을 최소의 메모리만 가지고 얻을 수 있습니다.
PS알못 OrbitHv의 PS