BOJ 9465 · 스티커

알고리즘 분류 : 다이나믹 프로그래밍  

스티커를 떼어내어 얻을 수 있는 최대 점수를 DP를 이용하여 구해야 한다.

• D[N][M] : N번째 열에서 스티커를 M했을 때, 2xN 개의 스티커에서 얻을 수 있는 최대 점수
• M = 0 (위쪽 스티커를 뜯음), M = 1 (아래쪽 스티커를 뜯음), M = 2 (둘 다 뜯지 않음)
• D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = 0
• D[N][0] : N번째 열에서 위쪽 스티커를 뜯어서 얻은 최대 점수
• D[N][1] : N번째 열에서 아래쪽 스티커를 뜯어서 얻은 최대 점수
• D[N][2] : N번째 열에서 둘 다 뜯지 않고 얻은 최대 점수

---

C++ 소스코드

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

int n, d[100001][3], p[100001][2];

void solve() {
    d[1][0] = p[1][0], d[1][1] = p[1][1], d[1][2] = 0;
    for (int i=2; i<=n; i++) {
        d[i][0] = max(d[i-1][1], d[i-1][2]) + p[i][0];
        d[i][1] = max(d[i-1][0], d[i-1][2]) + p[i][1];
        d[i][2] = max(max(d[i-1][0], d[i-1][1]), d[i-1][2]);
    }
    printf("%d\n", max(max(d[n][0], d[n][1]), d[n][2]));
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i=0; i<2; i++) {
            for (int j=1; j<=n; j++) {
                scanf("%d", &p[j][i]);
            }
        }
        solve();
    }
    return 0;
}

---

Python 3 소스코드

def solve():
    d[1][0], d[1][1] = p[0][1], p[1][1]
    for i in range(2, n+1):
        d[i][0] = max(d[i-1][1], d[i-1][2]) + p[0][i]
        d[i][1] = max(d[i-1][0], d[i-1][2]) + p[1][i]
        d[i][2] = max(d[i-1][0], d[i-1][1], d[i-1][2])

for _ in range(int(input())):
    n = int(input())
    p = [[0]+list(map(int, input().split())) for _ in range(2)]
    d = [[0]*3 for _ in range(n+1)]
    solve()
    print(max(d[n]))

---

참고

• 백준 온라인 저지 : BOJ 9465