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

문제 링크

9465번: 스티커

풀이

DP를 이용하는 문제

예시가 문제와 같이 다음 표라고 생각해보면

50	10	100	20	40
30	50	70	10	60

다음과 같이 생각할 수 있다.

50	10 + 30	100 + max(100, 30) = 200	20 + max(120, 100) = 140	40 + max(210, 120) = 250
30	50 + 50	70 + max(40, 50) = 120	10 + max(200, 40) = 210	60 + max(140, 200) = 260

정리하면, 해당 칸을 뜯는다고 가정할 때, 바로 대각선을 뜯을 것이냐 아니면 그 전 대각선을 뜯을 것이냐만 생각하면 된다.

점화식은 dp[0][j] = dp[0][j] + max(dp[1][j-1], dp[1][j-2])

 

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<vector<int>> dp(2, vector<int>(n));
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < n; k++)
            {
                cin >> dp[j][k];
            }
        }
        dp[0][1] += dp[1][0];
        dp[1][1] += dp[0][0];
        int answer = max(dp[0][1], dp[1][1]);
        for (int j = 2; j < n; j++)
        {
            dp[0][j] += max(dp[1][j - 1], dp[1][j - 2]);
            dp[1][j] += max(dp[0][j - 1], dp[0][j - 2]);
            answer = max(answer, dp[0][j]);
            answer = max(answer, dp[1][j]);
        }
        cout << answer << '\n';
    }
}