boj 2156 포도주 시식

dp로 인식하여 자력 솔브한 문제이기에 기록함 

해당 문제에 대해서 dp로 생각한 이유는 

이전 상태에 따라서 최대값이 달라지기 때문에 

 

현재 선택한 와인의 순번에 대하여

이전 상태에서 최대로 마실 수 있는 양과 적절한 계산을 통해

계산할 수 있을 것이라는 생각을 하게 됨 

 

문제에서 와인을 세번 연속 마실 수 없게 되어 있으므로 이에 대한 적절한 조치가 

달라질 것을 염두하였다.

 

문제설계
현재 순번의 선택 결과가 이전 선택 상태에 따라 달라지므로 DP 문제로 판단.
특히 3연속 불가 제약 때문에 이전 상태를 나누어 관리해야 한다고 생각함.

 

생각한 문제 패턴
이전 상태 기반 최대값 갱신 DP.
현재 와인을 마시는 경우 ,마시지 않는 경우를 나누고, 연속 선택 조건을 함께 고려

 

첫 접근했을 때 생각
현재 선택 와인 + 이전 단계 최대,

현재 선택 와인 + 전전 단계 최대,

현재 선택 안 함의 세 경우를 비교하면 된다고 판단함

3연속 금지 조건 때문에 직전 상태에 따른 분기 처리가 필요하다고 봄.

 

알고리즘

총 세가지 상태로 분기

i번째를 안 마시는 경우,

직전과 이어서 마시는 경우,

한 칸 띄우고 마시는 경우

각 상태에서 가능한 이전 최대값을 이용해 현재 최대값 갱신.

 

해결방법
현재 위치에서의 최대값을 이전 상태에 따라 분리하여 DP로 계산.
i번째를 안 마시는 경우, 직전과 이어 마시는 경우, 한 칸 띄우고 마시는 경우를 비교하여 최댓값 갱신.

 

개선할점
상태 정의를 더 명확하게 두면 점화식 의미가 더 분명해질 수 있음.
특히 안 마시는 상태도 이전 모든 상태의 최댓값을 받도록 정리하면 더 깔끔한 DP 설계가 가능함.

 

추가 탐구 부분
2차원 상태 DP 대신 1차원 점화식으로도 같은 문제를 풀 수 있는지 확인 

dp 상태 의미 처리에 있어서 가독성이 떨어지는데 앞으로 차츰 개선해 나가기

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin>>n;
	
	vector<int> list(n+1);
	
	for(int i=1; i<=n; i++)
	{
		cin>>list[i];
	}

	vector<vector<int>> dp(n+1, vector<int>(3,0));

	dp[1][0] = 0;
	dp[1][1] = list[1];
	dp[1][2] = list[1];

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


	cout<<max(max(dp[n][2],dp[n][1]), dp[n][0]);

}