[BOJ 2096] 내려가기

문제 링크 : https://www.acmicpc.net/problem/2096

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

제한

시간 제한	메모리 제한
1sec	4MB (하단 참고)

---

풀이

이전의 상태로부터 다음 상태의 결과를 얻어올 수 있다. 이전 위치와 현재 위치의 관계를 모식한 점화식을 통해 현재 위치의 최대 점수와 최소 점수를 계속해서 업데이트해나갈 수 있을 것 같다.

같은 줄에서 원룡이가 존재할 수 있는 위치는 총 3곳이다. 왼쪽 = 0, 중앙 = 1, 오른쪽 = 2라고 지정하자. 주어진 그림을 통해, 각 줄에 대해 점수를 이어나갈 수 있는 위치도 각각 정해진다. 수식으로 표현하면 아래와 같다.

\[\begin{aligned} left_{t} &= \min\big( left_{t-1}, center_{t-1} \big) + v_{left} \\ center_{t} &= \min\big( left_{t-1}, center_{t-1}, right_{t-1} \big) + v_{center} \\ right_{t} &= \min\big( center_{t-1}, right_{t-1} \big) + v_{right} \end{aligned}\]

이런 점화식은 다이나믹 프로그래밍에서 주로 보이는 패턴이다. 이 문제 또한 위 점화식을 활용한 DP 알고리즘으로 풀리는 문제이다. 문제에서는 각각의 최대 점수와 최소 점수를 계산하라고 하였으니, min() 함수에서 파라미터들로부터 최댓값과 최솟값을 업데이트할 수 있도록 구현하면 된다.

하지만 이것만으로는 부족하다. 메모리 제한이 4MB밖에 되지 않는다. 기존의 DP 방식으로 길이가 $N$인 배열을 만들면 메모리 초과가 발생할 수도 있다. 그래서 배열을 모두 만들지 말고 위 점화식을 구현하는 방법이 필요하다. 점화식을 다시 자세히 보면, 현재 line을 계산하기 위해 필요한 정보는 이전 line에서의 결과값만 있는 것을 알 수 있다. 그럼 배열의 길이를 $N$개 모두 할당하지 않고 현재 layer와 이전 layer를 current와 prev로 선언하여 이전 상태에 대한 정보를 저장하는 부분과 현재 상태를 계산하여 저장할 부분으로 나누어 계산하도록 하자. 이렇게 하면 int배열 총 6칸만 있으면 위 점화식을 수행하는 프로그램을 만들 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍