☆ 스티커 - 백준 9465

 

---

Problem

티어

실버 1

---

분류

Dynamic Programming(Bottom-Up)

---

접근

해결 못했었음

1) 첫 번째로 재귀(순열)로 접근(경우의 수가 기하급수적으로 되어버림),
2) DP 태그 보고 했는데 점화식 어떻게 세워야하는지 몰랐음.

걍 털림.. DP 너무 오랜만이라서 그런가..? 하고 변명을..

---

풀이

문제의 구조에서 점화식을 유도 해야했음.

이런 부분이 아직 많이 부족한 것 같다.

---

Solution

#include <iostream>
#include <vector>
using namespace std;

int n,t;
vector<vector<int>> dp;
vector<vector<int>> tmp;

int main()
{
    cin >> t;
    //Test Case Loop
    for (int i = 0; i < t; i++) {
        tmp.clear();
        dp.clear();
        cin >> n;
        for (int j = 0; j < 2; j++) {
            vector<int> line;
            tmp.push_back(line);
            for (int k = 0; k < n; k++) {
                int a;
                cin >> a;
                tmp[j].push_back(a);
            }
        }
        dp.push_back(vector<int>());
        dp.push_back(vector<int>());
        dp[0].push_back(tmp[0][0]);
        dp[1].push_back(tmp[1][0]);
        //dp[0][1]
        dp[0].push_back(tmp[0][1] + dp[1][0]);
        //dp[1][0]
        dp[1].push_back(tmp[1][1] + dp[0][0]);
        for (int p = 2; p < n; p++) {
            dp[0].push_back(tmp[0][p] + max(dp[1][p - 1], dp[1][p - 2]));
            dp[1].push_back(tmp[1][p] + max(dp[0][p - 1], dp[0][p - 2]));
        }
        cout << max(dp[0][n-1],dp[1][n-1]) << "\n";
        
    }
}