[C++]BOJ 9465 - 스티커

동적 계획법으로 해결할 수 있다.

따라서 두 번째 사진 처럼 짧은 대각선에 있거나 세 번째 사진처럼 긴 대각선에 있는 경우만 생각해주면 된다.

위 내용을 코드로 옮기면 아래와 같다.

#include <iostream>
using namespace std;
int t, n, dp[2][100001];
int main() {
	cin >> t;
	while(t--) {
		cin >> n;
		for(int i = 0; i < 2; i++)
			for(int j = 1; j <= n; j++)
				cin >> dp[i][j];
		for(int i = 2; i <= n; i++) {
			dp[0][i] += max(dp[1][i - 1], dp[1][i - 2]);
			dp[1][i] += max(dp[0][i - 1], dp[0][i - 2]);
		}
		cout << max(dp[0][n], max(dp[0][n - 1], max(dp[1][n], dp[1][n - 1]))) << endl;
	}
}

다른 사람 풀이를 보니 마지막에 dp[0][n]과 dp[1][n]만 비교해도 AC를 받았다.
나는 위 설명에서 3번째 사진과 같은 경우 때문에 마지막 4개를 비교했으나 안해도 되는 이유를 생각해봐야겠다.