9465번

9465 - 스티커

처음에 완전탐색 -> 시간초과

두번째 완전탐색을 DP로 변환 -> 실패

세번째 완전탐색 DP변환 -> 성공

두번째 완전탐색을 DP로 변환할 때, 

캐시는 2차원 배열이지만, 재귀함수는 sum값을 포함해서 넘겨주었다.

왠지 될 것 같았지만 오류가 발생하였다.

==> 문제점은 재귀호출은 N값을 뒤에서부터 1까지 갔다가 다시 1부터 축적해가면서 캐시를 저장하는 것인데,

 내가 작성한 코드는 N값을 뒤에서 1까지 갈 때 sum을 모두 저장하고 , 다시 앞에서부터 사용하기 때문에 생기는 문제.... 복잡하다..

 즉,  DP란 뒤에서 앞으로 왔다가 앞에서 뒤로 가는 과정인데, 함수에 sum 인자를 넣어서 return 하니 앞에서 뒤,앞에서 뒤가 되었다.

 나만 알아볼 수 있는 설명...ㅋㅋ

##재귀함수는 밑 부분 에서는 뒤에서 앞(N->1) , 기저 변수를 시작으로 앞에서 뒤 (1->N)##

점화식은 스티커를 위에만 붙이는 경우, 아래만 붙이는 경우, 붙이지 않는 경우를 나눠서

D[N][case] = N번째 스티커를 붙이는 case에 따라 최대점수.

<완전 탐색 코드 - 시간초과>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int ans;
int sticker[2][100001];
void calmax(int N, int cs, int sum)
{
    if (N <= 0)
    {
        ans = max(ans, sum);
        return;
    }
 
    if (cs == 0 || cs==1)
    {
        if (cs == 0)
        {
            calmax(N - 1, 1, sum + sticker[cs][N - 1]);
            calmax(N - 1, 2, sum + sticker[cs][N - 1]);
        }
 
        if (cs == 1)
        {
            calmax(N - 1, 0, sum + sticker[cs][N - 1]);
            calmax(N - 1, 2, sum + sticker[cs][N - 1]);
        }
        
    }
 
    if (cs == 2)
    {
        calmax(N - 1, 0, sum);
        calmax(N - 1, 1, sum);
        calmax(N - 1, 2, sum);
    }
 
    return;
 
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int n;
        
        ans = 0;
        memset(sticker, 0, sizeof(sticker));
 
 
        cin >> n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> sticker[i][j];
            }
        }
 
        for (int i = 0; i < 3; i++)
        {
            calmax(n, i, 0);
        }
    
        cout << ans << endl;
    }
 
    return 0;
}

<완전탐색에서 DP로 변환 실패>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int ans;
int sticker[2][100001];
int D[100001][3];
int calmax(int N, int cs, int sum)
{
    if (N == 0)
    {
        return sum;
    }
 
    if (D[N][cs] != -1)
    {
        return D[N][cs];
    }
 
    if (cs == 0 || cs==1)
    {
        if (cs == 0)
        {
            D[N][cs]=max(calmax(N - 1, 1, sum + sticker[cs][N - 1]),calmax(N - 1, 2, sum + sticker[cs][N - 1]));
        }
 
        if (cs == 1)
        {
            D[N][cs] = max(calmax(N - 1, 0, sum + sticker[cs][N - 1]),calmax(N - 1, 2, sum + sticker[cs][N - 1]));
        }
        
    }
 
    if (cs == 2)
    {
        D[N][cs] = max({ calmax(N - 1, 0, sum),calmax(N - 1, 1, sum),calmax(N - 1, 2, sum) });
    }
 
    return D[N][cs];
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int n;
        
        ans = 0;
        memset(sticker, 0, sizeof(sticker));
        memset(D, -1, sizeof(D));
 
 
        cin >> n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> sticker[i][j];
            }
        }
 
    
        cout << max({ calmax(n, 0, 0),calmax(n, 1, 0),calmax(n, 2, 0) }) << endl;
    }
 
    return 0;
}

<정답 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int ans;
int sticker[2][100001];
int D[100001][3];
int calmax(int N, int cs)
{
    if (N == 1)
    {
        if (cs != 2)
        {
            return sticker[cs][N - 1];
        }
        
        if (cs == 2)
        {
            return 0;
        }
    }
 
    if (D[N][cs] != 0)
    {
        return D[N][cs];
    }
 
 
    if (cs == 0)
    {
        D[N][cs] = max(calmax(N - 1, 1), calmax(N - 1, 2)) + sticker[cs][N - 1];
    }
 
    if (cs == 1)
    {
        D[N][cs] = max(calmax(N - 1, 0), calmax(N - 1, 2)) + sticker[cs][N - 1];
    }
 
    if (cs == 2)
    {
        D[N][cs] = max({ calmax(N - 1, 0),calmax(N - 1, 1),calmax(N - 1, 2) });
    }
 
    return D[N][cs];
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int n;
        memset(sticker, 0, sizeof(sticker));
        memset(D, 0, sizeof(D));
 
 
        cin >> n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> sticker[i][j];
            }
        }
 
    
        cout << max({ calmax(n, 0),calmax(n, 1),calmax(n, 2) }) << endl;
    }
 
    return 0;
}