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

🌽 문제

🥕 입출력

🥔 풀이

솔직히 완전히 이해는 못해서 다음에 다시 풀라고 하면 한참 걸릴 것 같다.
저번에 풀었던 계단 오르기와 비슷한 문제인데, 풀이 방식에는 약간의 차이가 있다.

이유는 문제 조건이 다르기 때문인데,
포도주가 0만큼 들어있을 수 있다는 점과
마지막 포도주를 마시지 않아도 된다는 점이 계단 오르기 문제와 다르다.
따라서 그래서 두 번 건너뛰는 경우도 고려해야 한다.

가능한 선택지는 아래와 같다.

1. 현재 포도주를 마시지 않는 경우
dp[i] = dp[i - 1]

2. 현재 포도주를 마시고, 이전(i-1) 포도주는 마시지 않는 경우
dp[i] = dp[i - 2] + gr[i]

3. 현재 포도주와 이전(i-1) 포도주를 모두 마시고, (i-2) 포도주는 마시지 않는 경우
dp[i] = dp[i - 3] + gr[i - 1] + gr[i]

🥬 코드

#include <iostream>
#include <algorithm>
using namespace std;

int gr[10001];
int dp[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> gr[i];

	dp[1] = gr[1];
	dp[2] = gr[1] + gr[2];
	dp[3] = max({ dp[2], gr[1] + gr[3], gr[2] + gr[3] });
	
    for (int i = 4; i <= n; i++) {
		dp[i] = max({ dp[i - 1], dp[i - 2] + gr[i], dp[i - 3] + gr[i - 1] + gr[i] });
	}

	cout << dp[n];
	return 0;
}

🥜 채점

실버도 어려우면 엇덕하니.