[BOJ/2156] 포도주 시식

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

 

문제 링크

- 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; } Colored by Color Scripter

cs