[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; } |