[BOJ]백준 2096번: 내려가기/DP

www.acmicpc.net/problem/2096

2096번: 내려가기

 

1. 문제 정의
N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다.
단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다.

2. Recursion&Subproblem
K-1번째 줄에서 1번을 선택했다면
K번째 줄에서 1, 2번 중 큰 숫자를 선택한다
K-1번째 줄에서 2번을 선택했다면
K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다
K-1번째 줄에서 3번을 선택했다면
K번째 줄에서 2,3번 중 큰 숫자를 선택한다

-> 이는 곧
K번째 줄에서 1번을 선택했다면
K-1번째 줄에서 1,2번 중 큰 숫자를 선택했던 경우이다.
K번째 줄에서 2번을 선택했다면
K-1번째 줄에서 1,2,3번 중 큰 숫자를 선택했던 경우이다.
K번째 줄에서 3번을 선택했다면
K-1번째 줄에서 2,3번 중 큰 숫자를 선택했던 경우이다.
를 의미한다.

3. Memoization&Recursion Relation
N*3 Array를 이용하여, DP의 중간 값을 저장한다.
이 때, K번째 줄의 DP value는 K-1에 dependent하므로, 0번째 행부터 증가하게 구한다.
0번째 행은 이전 행이 없으므로 0번째 배열 값이 그대로 dp value가 된다

4. Time Complexity
각각의 행에서 비교 회수는 2번, 3번, 2번이므로 O(1)이다.
N개의 행에 대해 이러한 연산을 반복하므로, O(N)*O(1) = O(N)이다.

최소 점수 연산 또한 위와 같다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, arr[100001][3], dp[100001][3];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++)scanf("%d", &arr[i][j]);
		if (!i) {
			for (int j = 0; j < 3; j++)dp[i][j] = arr[i][j];
			continue;
		}
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][0];
		dp[i][1] = max({ dp[i - 1][0],dp[i - 1][1],dp[i - 1][2] }) + arr[i][1];
		dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][2];
	}
	printf("%d ", max({ dp[n - 1][0],dp[n - 1][1],dp[n - 1][2] }));

	for (int i = 0; i < n; i++) {
		if (!i) continue;
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][0];
		dp[i][1] = min({ dp[i - 1][0],dp[i - 1][1],dp[i - 1][2] }) + arr[i][1];
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][2];
	}
	printf("%d", min({ dp[n - 1][0],dp[n - 1][1],dp[n - 1][2] }));
	return 0;
}