[백준 9465번] 스티커 (C++)

문제링크 : https://www.acmicpc.net/problem/9465

9465번: 스티커

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int dp[2][100001]; 

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

    int T, N;
    cin >> T;
    while(T--)
    {
        cin >> N;

        for(int i=0; i<N; i++)
        {
            cin >> dp[0][i];
        }

        for(int i=0; i<N; i++)
        {
            cin >> dp[1][i];
        }

        for(int i=1; i<N; i++)
        {
            dp[0][i] = dp[0][i] + max(dp[1][i-1], dp[1][i-2]);  //첫번째줄
            dp[1][i] = dp[1][i] + max(dp[0][i-1], dp[0][i-2]);  //두번째줄
        }

        cout << max(dp[0][N-1], dp[1][N-1]) <<'\n';
    }

    return 0;

}

dp 문제이다 경우가 2가지로 나뉜다.

첫 번째줄에서 대각선으로 계산한 것, 두 번째줄에서 대각선으로 계산한 것을 비교하면 된다.

여기서 주의할 것은 바로 1칸뒤의 대각선 뿐만이 아니라 2칸뒤의 대각선도 체크해줘야 한다.

 

다음 예제를 예시로 들자면

   0  1  2  3  4   5  6
0 10 30 10 50 100 20 40
1 20 40 30 50 60 20 80

 

만약 dp[0][2] -> 10을 기준으로 계산하자면

 

10 30 10 50 100 20 40
20 40 30 50 60 20 80

 

10 30 10 50 100 20 40
20 40 30 50 60 20 80

 

이렇게 2가지 경우의 수가 존재한다.

 

앞서서 dp[0 or 1][i-1]이 앞에 1칸 뒤의 대각선은 전부 계산해주기에 10 + 40 + 10 부분은 해결되고,

20 + 10의 경우는 2칸 뒤이므로 dp[0 or 1][i-2]이다.

이 둘중에서 더 큰 값을 저장해나가면 된다.