[BOJ 9465] 스티커

1) 문제 링크

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

2) 접근

처음에는 Bottom-up 방식으로 DP를 적용해서 문제를 풀려고 했다. 칸수를 적게 해서 차근차근 분석하다 보니 어떤 칸에 스티커를 붙이면, 그 칸과 다른 열의 한 행 앞의 칸 또는 두 행 앞의 칸에는 반드시 스티커가 붙음을 알 수 있었다.

빨강색에 붙였다면 초록색 칸 중 하나에는 반드시 붙음

그래서, 맨 왼쪽 위부터 시작하는 경우, 맨 왼쪽 아래부터 시작하는 경우의 2가지로 나누어서 코드를 짰다. 근데… 코드를 약간만 바꾸니까 틀렸던 게 맞았다. 뭐지???

3) 풀이

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t, n;
    cin >> t;

    for(int idx=0; idx<t; ++idx){
        cin >> n;

        int stickers[2][100000] = {0};
        int score[2][100000] = {0};

        for(int i=0; i<2; ++i){
            for(int j=0; j<n; ++j){
                cin >> stickers[i][j];
            }
        }

        score[0][0] = stickers[0][0];
        score[1][0] = stickers[1][0];

        int col=0;
        for(int i=0; i<n-1; ++i){
            col ^= 1;
            if(i+1<n){ score[col][i+1] = max(score[col][i+1], score[(col+1)%2][i]+stickers[col][i+1]); }
            if(i+2<n){ score[col][i+2] = max(score[col][i+2], score[(col+1)%2][i]+stickers[col][i+2]); }
        }

        col=1;
        for(int i=0; i<n-1; ++i){
            col ^= 1;
            if(i+1<n){ score[col][i+1] = max(score[col][i+1], score[(col+1)%2][i]+stickers[col][i+1]); }
            if(i+2<n){ score[col][i+2] = max(score[col][i+2], score[(col+1)%2][i]+stickers[col][i+2]); }
        }

        cout << max(score[0][n-1], score[1][n-1]) << endl;
    }

    return 0;
}

아 ㅋㅋ 어림도 없지 땡~~

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t, n;
    cin >> t;

    for(int idx=0; idx<t; ++idx){
        cin >> n;

        int stickers[2][100000] = {0};
        int score[2][100000] = {0};

        for(int i=0; i<2; ++i){
            for(int j=0; j<n; ++j){
                cin >> stickers[i][j];
            }
        }

        score[0][0] = stickers[0][0];
        score[1][0] = stickers[1][0];

        for(int i=0; i<n-1; ++i){
            if(i+1<n){
                score[1][i+1] = max(score[1][i+1], score[0][i]+stickers[1][i+1]);
                score[0][i+1] = max(score[0][i+1], score[1][i]+stickers[0][i+1]);
            }
            if(i+2<n){
                score[1][i+2] = max(score[1][i+2], score[0][i]+stickers[1][i+2]);
                score[0][i+2] = max(score[0][i+2], score[1][i]+stickers[0][i+2]);
            }
        }

        cout << max(score[0][n-1], score[1][n-1]) << endl;
    }

    return 0;
}

4) 피드백

두 코드의 차이점
많은 사람들이 짜는 방식의 DP(Top-down, Bottom-Up 모두)
알아보고 쓸 예정.