[백준][DP] 스티커

1. 문제 주소

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

9465번: 스티커

2. 문제

2차원 배열을 이용하여 스티커의 점수를 입력을 받는다. 그리고 스티커를 하나도 떼지 않는 경우, 첫 번째 줄에서 떼는 경우, 두 번째 줄에서 떼는 경우에서의 점수를 구한 후 최댓값을 출력을 하면 된다.

3.소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int score[100001][2];
int dp[100001][3];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        for (int i = 1; i <= n; i++)
            cin >> score[i][0];
 
        for (int i = 1; i <= n; i++)
            cin >> score[i][1];
 
 
        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])); //떼지 않는 경우
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + score[i][0]; // 첫 번째 줄에서 떼는 경우
            dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + score[i][1]; // 두 번째 줄에서 떼는 경우
        }
        
        int result = 0;
        for (int i = 1; i <= n; i++)
            result = max(max(result, dp[i][0]), max(dp[i][1], dp[i][2]));
        
        cout << result << '\n';        
    }
 
    return 0;
}