Algorithm/Problem Solving
[BOJ/2156] 포도주 시식
DevMoomin
2020. 4. 17. 20:50
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/2156
사용 알고리즘
- DP
풀이
- d[i][j] = i번째 포도주까지 마셨을 때의 최대 포도주의 양. i번째 포도주는 j번 연속으로 마심
- d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2])
- d[i][1] = d[i - 1][0] + p[i]
- d[i][2] = d[i - 1][1] + p[i]
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/2156.cpp
|
#include <cstdio>
#include <algorithm>
using namespace std;
int d[10003][3];
int p[10003];
int main(void) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
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] = d[i - 1][0] + p[i];
d[i][2] = d[i - 1][1] + p[i];
}
printf("%d\n", max(d[n][0], max(d[n][1], d[n][2])));
return 0;
}
|