BOJ (C/C++) 2156번: 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

풀이

3잔을 연속으로 마시면 안 되므로 3번째 잔부터 조건을 고려해줌

?OOX - DP[i-1]

?XOO - DP[i-3]+wine[i-1]+wine[i]

?OXO - DP[i-2]+wine[i]

 

i번째 순서에 최대값이 나올 조건은 위의 3개이므로 이를 고려하여 DP로 코드를 구현

 

밑의 링크의 설명이 자세해서 문제 풀 때 도움을 많이 얻었다!

https://yabmoons.tistory.com/512

[ 백준 2156 ] 포도주 시식 (C++)

---

코드

#include <stdio.h>
int Max(int a, int b) {
	if (a > b) return a;
	return b;
}
int main() {
	int n;
	int wine[10000], DP[10000];
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &wine[i]);

	DP[1] = wine[1], DP[2] = wine[1] + wine[2];

	for (int i = 3; i < n; i++) {
		DP[i] = Max(DP[i - 1], Max(DP[i - 3] + wine[i - 1] + wine[i], DP[i - 2] + wine[i]));
	}

	printf("%d", DP[n - 1]);
	return 0;
}