9465번 : 스티커

까다롭게 보이지만, 실제로는 전혀 까다롭지 않다.

행은 2행으로 고정되어있고 열이 유동적이니 1열부터 n열까지 dp를 채워나가면 될 것 같다.

각 열마나 선택지가 총 3개가 있다. 아무것도 선택하지 않거나, 1행을 선택하거나 2행을 선택하는 것이다.

i번째 열에서 아무것도 선택하지 않을 때 dp에는 dp[i][0]으로 들어간다.

1행을 선택하면 dp[i][1], 2행을 선택하면 dp[i][2]로 들어간다.

편의상 MAX(a, b)는 a와 b중 더 큰값을 반환하고, MAX3(a, b, c)는 a, b, c 중 제일 큰값을 반환한다.

1) 아무것도 선택하지 않을 때 그 이전 열까지 합이 최대가 되는 dp의 값을 그대로 갖는다.

ex)dp[3][0]=MAX3(dp[2][0], dp[2][1]. dp[2][2])가 된다.

2) 1행을 선택했을 때는 이전 열에서 아무것도 선택하지 않았을 때와 2번째 행을 선택했을 경우 두가지 중 하나를 갖는다.

ex)dp[3][1]=MAX(dp[2][0], dp[2][2]);

3) 2행을 선택했을 때는 이전 열에서 아무것도 선택하지 않았을 때와 1번째 행을 선택했을 경우 두가지 중 하나를 갖는다.

     ex)dp[3][2]=MAX(dp[2][0]. dp[2][1]);

마지막으로 값을 출력할 때는 dp[N][0], dp[N][1], dp[N][2] 중 가장 큰 하나를 골라주면 된다.

#include <stdio.h>

int N, dp[100001][3], arr[100001][3];

/*

dp[i][0] : 아무것도 선택 x

dp[i][1] : 첫 번째꺼 선택

dp[i][2] : 두 번째꺼 선택

*/

int MAX(int a, int b) {

return a > b ? a : b;

}

int MAX3(int a, int b, int c) {

return MAX(a, MAX(b, c));

}

int main() {

int T;

scanf("%d", &T);

while (T--) {

for (int i = 1; i <= N; ++i) {

for (int j = 0; j <= 2; ++j) {

dp[i][j] = 0;

arr[i][j] = 0;

}

}

scanf("%d", &N);

for (int i = 1; i <= 2; ++i) {

for (int j = 1; j <= N; ++j) {

scanf("%d", &arr[j][i]);

}

}

dp[1][0] = 0;

dp[1][1] = arr[1][1];

dp[1][2] = arr[1][2];

for (int i = 2; i <= N; ++i) {

dp[i][0] = MAX3(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);

dp[i][1] = MAX(dp[i - 1][2], dp[i - 1][0])+arr[i][1];

dp[i][2] = MAX(dp[i - 1][1], dp[i - 1][0])+arr[i][2];

}

printf("%d\n", MAX3(dp[N][0], dp[N][1], dp[N][2]));

}

}