백준 9465 - 스티커

문제

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

9465번: 스티커

 

풀이

첫 번째 열에서 스티커를 떼지 않으면 두 번째 열에서 가능한 선택은 세가지다. 위 스티커를 떼거나 아래 스티커를 떼거나 스티커를 떼지 않는 경우가 된다. 첫 번째 열에서 위쪽 스티커를 떼면 두 번째 열은 아래쪽 스티커 또는 아무것도 떼지 않을 수 있다. 반대로 첫 번째 열에서 아래쪽 스티커를 떼면 두 번째 열은 위쪽 스티커 또는 아무것도 떼지 않을 수 있다.

 

이 특성을 이용해 status 변수를 사용해 상태를 나타낸다. 0이면 왼쪽 열에서 아무것도 떼지 않은 경우, 1인 경우 왼쪽 열의 위 스티커를 뗀 경우, 2인 경우 왼쪽 열에서 아래 스티커를 뗀 경우다. 이 세가지 경우 중 최대가 되는 경우를 답으로 선택하면 된다.

 

sticker(c, status)이 있을 때, c는 스티커 중 c번 열부터만 스티커를 떼어내서 얻을 수 있는 최대 가치를 구하는 거다.

 

코드

탑다운 방식

#include <iostream>
#include <algorithm>
using namespace std;
 
const int MAX = 100000;
 
int N;
int dp[MAX][3];
int score[2][MAX];
 
int sticker(int c, int status)
{
    if (c == N) return 0;
    if (dp[c][status] != -1) return dp[c][status];
 
    int result = sticker(c + 1, 0);
    if (status != 1) result = max(result, sticker(c + 1, 1) + score[0][c]);
    if (status != 2) result = max(result, sticker(c + 1, 2) + score[1][c]);
 
    dp[c][status] = result;
    return result;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> N;
 
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < N; k++)
                cin >> score[j][k];
 
        for (int j = 0; j < N; j++)
            for (int k = 0; k < 3; k++)
                dp[j][k] = -1;
        
        cout << sticker(0, 0) << '\n';
    }
 
    return 0;
}

 

바텀업 방식

#include <iostream>;
#include <algorithm>;
 
using namespace std;
 
int dp[100001][3];
int score[2][100001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int k = 0; k < n; k++)
    {
        int N;
        cin >> N;
        
        for (int i = 0; i < 100001; i++)
            for (int j = 0; j < 3; j++)
                dp[i][j] = 0;
 
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < N; j++)
                cin >> score[i][j];
 
        for (int i = 0; i < N; i++)
        {
            dp[i + 1][0] = max(dp[i + 1][0], max(dp[i][0], max(dp[i][1], dp[i][2])));
            dp[i + 1][1] = max(dp[i + 1][1], max(dp[i][0], dp[i][2]) + score[0][i]);
            dp[i + 1][2] = max(dp[i + 1][2], max(dp[i][0], dp[i][1]) + score[1][i]);
        }
 
        cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << '\n';
    }
 
    return 0;
}

점수의 최소값이 0이므로 0으로 초기화 해준다.