[백준/BOJ] 2156 - 포도주 시식 (c++) (DP)

1. 문제

 

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

---

2. 풀이

이 문제는 DP를 이용하여 푸는 문제이다.

 

중요한점은 dp[i]를 i번째 포도주(자기자신)을 먹은 여부에 따라 설정하는 것이다.

 

일단 첫번째로 i번째 포도주(자기자신)을 먹었다고 한다면

 

i번째 포도주(자기자신)을 먹었기 때문에

 

i-1번째 포도주를 안 먹었다면 dp[i] = dp[i-2] + arr[i]이다.

 

i-1번째 포도주를 먹었다면 dp[i] = dp[i-3] + arr[i-1] + arr[i]이다.

 

두번째로 i번째 포도주(자기자신)를 안먹었다고한다면

 

i-1번째 포도주를 먹든 안먹든 상관이 없어지기 때문에 dp[i]는 dp[i-1]이게 된다.

 

즉

 

dp[0] = 0, dp[1] = arr[1], dp[2] = dp[0] + dp[1]

 

i>=3, dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i], dp[i-1])

 

이렇게 점화식이 세워진다.

---

3. 소스코드

#include <iostream>

using namespace std;

int n, arr[10001], dp[10001];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	
	dp[0] = 0;
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int i = 3; i <= n; i++) 
		dp[i] = max(dp[i - 1], max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));

	cout << dp[n];
}

 

---

4. 참고

https://mygumi.tistory.com/98

---

질문, 고칠점 등 댓글 언제나 환영입니다.