[알고리즘] 백준 2156 포도주 시식

📖문제

2156 포도주 시식

💡구상

먼저 문제의 조건을 살펴보자.

• 1부터 N까지의 번호가 붙어있는 N개의 포도주 잔을 선택해서 마셔야한다.
• 연속으로 놓여있는 3잔을 마실 수 없다.
• 1<=N<=10,000

위 조건을 바탕으로 DP를 가장 먼저 생각했고, 아래와 같은 코드를 구상하였다.

int go(int now,int prev){
	if(now >= n+1) return 0;
	
	int &ret = dp[now][prev];
	if(ret) return ret;
	
	// 연속으로 3잔을 마시는 것을 방지하는 로직
	
	return ret; 
}

위는 현재 선택한 idx와 이전 idx를 DP배열의 원소로 선택하여 최댓값을 저장해나가려고 했다.

하지만 문제의 조건을 살펴보면 N은 최대 10,000이므로 DP배열의 공간복잡도가 초과하게된다.

그럼 재귀를 이용하지 않고 간단하게 점화식을 세울 수는 없을까?

🔍코드

#include<bits/stdc++.h> 
using namespace std;
int n,a[10001];
int dp[10001];
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	
	// N이 2 이하인 경우 
	dp[1]=a[1];
	dp[2]=a[1]+a[2];
	// N이 3 이상인 경우 
	for(int i=3; i<=n; i++){
		dp[i] = max(dp[i-3]+a[i-1]+a[i],dp[i-2]+a[i]);
		dp[i] = max(dp[i-1],dp[i]);
	}
	cout<<dp[n];
}

DP 배열에 최댓값을 계속해서 저장해간다면?

N이 1,2 인 경우

우선 N이 1,2인 경우는 최대 2개까지 이어서 선택이 가능하므로 모두 담는 경우가 최댓값일 것이다.

N이 3 이상인 경우

N이 3인 경우를 생각해보자.
1. 1,2를 고르는 경우
2. 1,3을 고르는 경우
3. 2,3을 고르는 경우
3가지의 경우의 수가 존재한다.

이를 점화식으로 나타내면

// 1. 1,2를 고르는 경우
DP[N] = DP[N-1]
// 2. 1,3을 고르는 경우
DP[N] = DP[N-2]+A[N]
// 3. 2,3을 고르는 경우
DP[N] = DP[N-3]+A[N-1]+A[N]

위와 같이 나타낼 수 있다.

이처럼 N이 1,2 인 경우와 3 이상인 경우를 분리하여 N까지의 DP값을 구할 수 있다.

🔥배운 점

DP에서 공간 복잡도 문제로 재귀를 사용할 수 없을때는 해당 문제가 점화식으로 일반화 할 수 있는지 먼저 살펴보자!