백준 9465 스티커

백준 9465 스티커

 

9465번: 스티커

​

dp문제 2차원 dp로 풀었다.

한번뗀 스티커의 오른쪽 왼쪽 아래쪽은 사용할 수 없다.

dp[n][0] => n번째 행의 스티커를 안뗀 경우 dp[n][1] => n번째 행의 스티커를 뗀 경우

그래서 처음에는 지그재그로 다 떼면 어차피 양수니까 최대한 많이 뗄 수록 좋다고 생각했는데

예제로 나온 테스트 케이스를 보면서 깨달은게 마지막에 떼는 스티커의 점수가 매우 크면

지그재그로 2개뗀거 보다 더 클 수도 있다.

그래서  max(dp[i - 2][0], dp[i - 2][1], dp[i - 1][1]) 이런식으로 비교해주었음

그렇게 푸니까 정답​

 

 

#include <iostream>
​
using namespace std;
​
int max(int a, int b, int c)
{
    int max = a;
    if (max < b)
        max = b;
    if (max < c)
        max = c;
    return max;
}
​
int main(void)
{
    int t;
    int s[2][100001];
    int dp[100001][2];
​
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < 2; ++i) {
            for (int j = 1; j <= n; ++j)
                cin >> s[i][j];
        }
​
        dp[1][0] = s[0][1];
        dp[1][1] = s[1][1];
        
        if (n > 1) {
            dp[2][0] = dp[1][1] + s[0][2];
            dp[2][1] = dp[1][0] + s[1][2];
​
            int max_dp = dp[2][0] > dp[2][1] ? dp[2][0] : dp[2][1];
            for (int i = 3; i <= n; ++i) {
                dp[i][0] = max(dp[i - 2][0], dp[i - 2][1], dp[i - 1][1]) + s[0][i];
                if (max_dp < dp[i][0]) max_dp = dp[i][0];
                dp[i][1] = max(dp[i - 2][0], dp[i - 2][1], dp[i - 1][0]) + s[1][i];
                if (max_dp < dp[i][1]) max_dp = dp[i][1];
            }
​
            cout << max_dp << endl;
        }
        else
            cout << (dp[1][0] > dp[1][1] ? dp[1][0] : dp[1][1]) << endl;
    }
​
    return 0;
}​