(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- 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; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
[BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
---|---|
[BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
[BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
[BOJ/11057] 오르막 수 (0) | 2020.04.16 |
[BOJ/10844] 쉬운 계단 수 (0) | 2020.04.14 |