백준 9456 - 스티커 [C/C++]

9465번: 스티커 (acmicpc.net)

문제 예시

입력 및 출력 예시

 

스티커가 2중 배열로 제한 되어 있다는 점에서 알고리즘을 생각해 내는 것은 어렵지 않았다.

 

옆으로 나열 되는 수만 input으로 주어질 뿐, 위 아래 배열은 고정되어 있다는 점에서, 무조건 Dynamic Programming을 써야 한다는 것을 눈치채야 한다.

 

간단히 생각해 보자면, 내가 바로 n번째에 고른 스티커를 윗 배열 거를 골랐다면, 다음 n+1번째 스티커 순열의 경우의 수는 

• 아랫 배열 거를 고르거나,
• n번째 골랐던 거와는 상관없이 n-1번째 골랐던 스티커의 최대 순열의 점수      +     n+1번째 순열의 위 아래 상관없이 고르기

가 될 것이다.

 

아래는 내가 작성한 C++ 코드이다.

#include <iostream>


using namespace std;

int dp[2][100000];
int mp[2][100000];
int testcase, num;
int before = 0;

void solve(){
    dp[0][0] = mp[0][0];
    dp[1][0] = mp[1][0];
    dp[0][1] = dp[1][0] + mp[0][1];
    dp[1][1] = dp[0][0] + mp[1][1];

    for (int i = 2; i < num; i++)
    {
        dp[0][i] = max(max(dp[1][i-1]+mp[0][i],dp[0][i-2]+mp[0][i]),dp[1][i-2]+mp[0][i]);
        dp[1][i] = max(max(dp[0][i-1]+mp[1][i],dp[0][i-2]+mp[1][i]),dp[1][i-2]+mp[1][i]);
    }
    cout << max(dp[0][num-1],dp[1][num-1]) << endl;
}

int main() {

    cin >> testcase;
    while(testcase>0){
        testcase--;
        cin >> num;
        for (int i = 0; i < num; i++)
        {
            cin >> mp[0][i];
        }
        for (int i = 0; i < num; i++)
        {
            cin >> mp[1][i];
        }
        solve();
    }
    return 0;
}