[백준][dp] 9465 스티커 c++구현

목차

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

문제

 

 

문제 구현 시 주의점

1. 3개 값을 비교하고 싶다면 max를 중첩하자 처음에 아무생각 없이 max안에 인수를 3개 넣어서 무한 오류..
2. scanf와 cout 를 혼용하면 안된다 즉 c와 c++혼용해서는 안된다.
3. 저런 케이스는 개행문자를 꼭 써주어야 한다.

 

코드 구현 방향

an1 an2를 구한 뒤 그후부터는 그 전값과 그 전전 값을 비교해서 가장 큰 값을 취해주어 누적하는 방식으로 풀었다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;


typedef long long ll;
vector<int>arr[2];
vector<string>v;
vector<int> ans;
int N, cnt, num;


long long mfunc(int size) {
    vector<ll> dp[2];

    dp[0].push_back(arr[0][0]);
    dp[1].push_back(arr[1][0]);

    if (size == 1)
        return max(dp[0][0], dp[1][0]);
    int a= max(dp[0][0], dp[1][0]);
    dp[0].push_back(arr[0][1]+ arr[1][0]);
    dp[1].push_back(arr[1][1]+ arr[0][0]);

    if (size == 2)
        return  max(dp[0][1], dp[1][1]);

    for (int i = 2; i < size; i++) {
        dp[0].push_back(arr[0][i] + max(max(dp[0][i - 2], dp[1][i - 1]), dp[1][i - 2]));
        dp[1].push_back(arr[1][i] + max(max(dp[1][i - 2], dp[0][i - 1]), dp[0][i - 2]));
    }
    return max(dp[0][size - 1], dp[1][size - 1]);
   
}

void split(string input, string delimiter) {
    long long int pos;
    string token;
    while ((pos = input.find(delimiter)) != string::npos) {
        token = input.substr(0, pos);
        v.push_back(token);
        input.erase(0, pos + delimiter.length());
    }
    v.push_back(input);

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> cnt;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < cnt; k++) {
                cin >> num;
                arr[j].push_back(num);
             }

        }
        cout << mfunc(cnt)<<'\n';
        arr[0].clear();
        arr[1].clear();
        
    }
  

}