# 백준 : 스티거(9465)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_9465_sticker)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

int sticker[2][100001];
int dp[2][100001];

void init() {
    for(int i=0; i<2; i++) {
        for(int j=0; j<100001; j++) {
            dp[i][j] = sticker[i][j] = 0;
        }
    }
}

int main(void)
{
    int problems;
    int values;
    int number;
    int result, maximum;
    
    cin>>problems;
    for(int p = 0; p<problems; p++) {
        cin>>values;
        if(p > 0) init();
        
        for(int line = 0; line<2; line++) {
            for(int v = 0; v<values; v++) {
                cin>>number;
                sticker[line][v + 1] = number;
            }
        }
        
        maximum = 0;
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = sticker[0][1];
        dp[1][1] = sticker[1][1];
        
        for(int i = 2; i<=values; i++) {
            dp[0][i]    = max(dp[1][i-1], dp[1][i-2]) + sticker[0][i];
            dp[1][i]    = max(dp[0][i-1], dp[0][i-2]) + sticker[1][i];
            result      = max(dp[0][i], dp[1][i]);
        }
        cout<<max(dp[0][values], dp[1][values])<<endl;
    }
    return 0;
}

풀이

DP 문제 중 한가지에 도전하다가 쓰디쓴 패배를 맛보고 어떤 블로그(여기)에서 DP 실력 향상에 도움이 된다고 추천한 문제들을 풀어보기로 하였다. 첫번째 문제인 1 만들기는 지난번에 포스팅하기도 했고, 다시 풀었을 때 크게 어려움이 없어서 넘어갔고 다음 문제인 스티커를 풀어보았다.
내가 DP를 풀면서 느끼는 것은 '생각이 거기까지 미치지 못하는구나' 였다. 문제는 해답을 보아도 왜 이건지 이해하지 못하는 경우도 있고.. 결국 계속 풀어보면서 내 생각의 범위를 넓히는 수 밖에는 없을 것 같다.
이번 풀이는 이곳 블로그를 참조하였다. 자세한 해설은 이곳을 보면 알 수 있을 것 같다. 

나는 이 문제를 다시한번 내 힘으로 풀어보면서 점화식 세우는 연습을 계속 해나가야 할 것 같다.

어떠한 점화식을 사용했는지는 여기에 적기엔 아직 부끄러우니 해결에 도움을 준 블로그만 링크로 남기도록 한다.