[DP/중~중하] 9465번 스티커

요즘 문제 풀면서 느끼는건데 실력이 좀 는거같다 내가 생각한대로 알고리즘 짜면 테스트 케이스는 웬만하면 다 나오는편인것 같아서 뿌듯하다.

dp[i][1] -> i 번째 열의 첫번째 행 원소를 택하는 경우

dp[i][2] -> i번째 열의 두번째 행 원소를 택하는 경우

dp[i][3] -> i번째 열의 원소를 아무것도 선택하지 않는 경우 를 나타낸것이다.

dp[2][1] -> 1행 2열의 원소를 택했을때 얻을수있는 최대 점수 -> 30을 택하고 20을 택하면 되므로 50

dp[2][2]- > 2행 2열의 원소를 택했을때 얻을수 있는 최대 점수 -> 40을 택하고 10을 택하면 되므로 합이 50

dp[2][3] -> 2열의 원소를 아무것도 택하지 않았을때 최대 점수 -> 그열의 전열까지의최대점수 ->dp[1][1],dp[1][2]중 최대를 고르면 되므로 20

...

이런식으로 쭉 알고리즘을 짜게 되면 마지막줄 처럼 dp[7][1] dp[7][2] dp [7][3]의 값이 나오는데 이 값들중 최대값을 고르면 그게 정답이다.

전체 소스 코드

#include<iostream>
#include<algorithm>
#include<memory.h>
#include<vector>
using namespace std;
vector<int> result;
int main()
{
    
    int n;
    cin>>n;
    while(n-- > 0)
    {
        int m;
        cin>>m;
        int input[3][100001];
        int dp[100001][4];
        memset(input,0,100001*sizeof(int));
        memset(dp,0,100001*sizeof(int));
        
        for(int i=1; i<=2; i++)
            for(int j=1; j<=m; j++)
                cin>>input[i][j];
        
        dp[1][1] = input[1][1];
        dp[1][2] = input[2][1];
        dp[1][3] = 0;
        for(int i=2; i<=m; i++)
        {
            dp[i][1] = max(dp[i-1][2] + input[1][i],dp[i-1][3]+input[1][i]);
            dp[i][2] = max(dp[i-1][1]+input[2][i],dp[i-1][3]+input[2][i]);
            dp[i][3] = max(dp[i-1][1],dp[i-1][2]);
        }
        result.push_back(max(max(dp[m][1],dp[m][2]),max(dp[m][2],dp[m][3])));
    }
    
    for(int i=0; i<result.size(); i++)
        cout<<result[i]<<endl;
    return 0;
}