[BOJ 9465] 스티커

출처 : https://www.acmicpc.net/problem/9465

1. dp를 통해 스티커 위->아래->오른쪽을 돌며 계산한다.

#include <iostream>

#include <algorithm>

using namespace std;

#define MAX_N 100002

int i, j, T, N;

int cost[2][MAX_N], dp[2][MAX_N], result;

void input()

{

cin >> N;

for (i = 0;i <= 1;i++)

{

for (j = 0;j <= N + 1;j++)

{

if (j >= 2) 

{ 

cin >> cost[i][j]; 

}else 

{ 

cost[i][j] = 0; 

}

dp[i][j] = 0;

}

}

}

void cal()

{

for (j = 2;j <= N + 1;j++)

{

dp[0][j] = max(dp[1][j-1], dp[1][j-2]) + cost[0][j];

dp[1][j] = max(dp[0][j-1], dp[0][j-2]) + cost[1][j];

}

result = max(dp[1][N+1], dp[0][N+1]);

}

int main()

{

cin >> T;

while (T--) 

{

input(); cal();

cout << result << endl;

}

}