[BOJ/9465] 스티커

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i][j] = 2 * i개의 스티커에서 얻을 수 있는 최대점수, i번째 열에서 뜯는 스티커는 j

- d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2]) (j = 0 : 위, 아래 모두 뜯지 않음)

- d[i][1] = max(d[i - 1][0], d[i - 1][2]) + p[i][0] (j = 1 : 위만 뜯음)

- d[i][2] = max(d[i - 1][0], d[i - 1][1]) + p[i][1] (j = 2 : 아래만 뜯음)

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/9465.cpp

#include <cstdio> #include <algorithm>   using namespace std;   int d[100003][3]; int arr[100003][2];   int main(void) {     int t; for (scanf("%d", &t); t--;) {         int n; scanf("%d", &n);         for (int i = 0; i < n; ++i) scanf("%d", &arr[i][0]);         for (int i = 0; i < n; ++i) scanf("%d", &arr[i][1]);         d[0][1] = arr[0][0]; d[0][2] = arr[0][1];         for (int i = 1; i < n; ++i) {             d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));             d[i][1] = max(d[i - 1][0], d[i - 1][2]) + arr[i][0];             d[i][2] = max(d[i - 1][0], d[i - 1][1]) + arr[i][1];         }         printf("%d\n", max(d[n - 1][0], max(d[n - 1][1], d[n - 1][2])));     }     return 0; } Colored by Color Scripter

cs