[백준/C,C++] 9465번: 스티커

www.acmicpc.net/problem/9465

9465번: 스티커

풀이

많이 등장하는 비교적 쉬운 난이도의 DP 문제입니다

 

 

100에 해당하는 스티커를 떼야 한다고 생각해 봅시다.

 

빨간색으로 동그라미 쳐진 스티커 두장을 떼고 100점 짜리 스티커를 떼거나

 

파란색으로 동그라미 쳐진 스티커를 떼고 100점 짜리 스티커를 떼는 방법이 있을 겁니다.

 

빨간색으로 동그라미 쳐진 스티커를 한장만 떼고 100점 짜리 스티커를 떼는 방법은 고려하지 않아도 됩니다.

 

두 번째 50점짜리 스티커를 떼도 100점 짜리 스티커를 뗄 수 있기 때문이죠.

 

 

그럼 행을 y, 열을 x 라고 했을 때, 다음과 같은 점화식을 세울 수 있습니다.

 

$DP[y][x] = max(DP[y][x - 1], DP[y][x - 2]) + st[y][x]$

 

#include<iostream>

using namespace std;

#define MAX 100001

int DP[2][MAX];
int st[2][MAX];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t; cin >> t;

    for (int i = 0; i < t; i++) {
        int n; cin >> n;
        for (int j = 1; j <= n; j++) {
            cin >> st[0][j];
        }
        for (int j = 1; j <= n; j++) {
            cin >> st[1][j];
        }
        DP[0][1] = st[0][1];
        DP[1][1] = st[1][1];
        for (int j = 2; j <= n; j++) {
            DP[0][j] = max(DP[1][j - 1], DP[1][j - 2]) + st[0][j];
            DP[1][j] = max(DP[0][j - 1], DP[0][j - 2]) + st[1][j];
        }

        cout << max(DP[0][n], DP[1][n]) << '\n';
    }

    return 0;
}

반례

Input

3
6
10 40 70 80 90 150
50 20 80 160 20 10
8
9 1 8 3 4 7 0 4
0 0 0 0 0 0 0 0
10
100 99 100 99 100 100 100 100 99 99
99 99 99 100 100 100 100 99 99 99

Output

430

28

996