2156번

2156번 - 포도주 시식

완전탐색 후 -> DP변환

완전 탐색 코드는 시간 초과

DP로 변환하는 과정에서 다양한 실수

실수 1. 기저 조건을 좀 더 명확하고 세세하게 정의 할 것. 빠뜨린 것이 없도록.

=> 모든 인자에 대해서 확인할 것.

이번 문제에서 n값만 확인하고 left 인자에 대해서는 기저 조건에서 빠뜨린 부분이 존재했다.

실수 2. 출력 값을 정확하게 확인할 것.

=> 맨 마지막 잔을 먹을 때, 먹지 않을 때 다 비교해서 출력해야 하는데

맨 마지막 잔은 항상 먹는 것으로 착각해서 처음에 drink(n,2) 값만 출력했었다.

실수 3. 인덱스 범위를 확실히 할 것.

=> 이번 문제에서 포도잔을 0번이 아닌 1번 부터로 계산했는데 머릿속으로만 그렇게 하고

실제 코드에서는 입력부터 1~n-1 까지만 받았었고

포도잔 마시는 것도 n번째 잔을 마시는게 아닌 n-1 잔을 마시는 것으로 코딩했다.

점화식 

D[N][left] = N번째 잔이 연속 된 잔 중에 몇번째 인가?

D[N][2] = N번째 잔은 마실 수 있고 N번째 잔을 포함해서 앞으로 2잔을 마실 수 있다.

D[N][0] = N번째 잔은 마실 수 없다. N번째 잔을 포함해서 앞으로 0잔을 마실을 마실 수 있으므로.

<완전 탐색 코드 - 시간 초과>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int glass[10001];
int ans;
void drink(int N,int left,int sum)
{
	if (N == 0)
	{
		ans = max(sum, ans);
		return;
	}
	if (left>=1)
	{
		drink(N - 1, left - 1, sum + glass[N - 1]);
		drink(N - 1, 2, sum);
	}
	else if (left == 0)
	{
		drink(N - 1, 2, sum);
	}
	return;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> glass[i];
	}
	drink(n,2,0);
	cout << ans << endl;
	return 0;
}

<완성 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
 
int glass[10001];
int D[10001][3];
int ans;
 
int drink(int N,int left)
{
    if (N == 1 && left == 0)
    {
        return 0;
    }
    if (N == 1 && left !=0)
    {
        return glass[N];
    }
    if (D[N][left] != 0)
    {
        return D[N][left];
    }
 
    if (left>=1)
    {
        D[N][left]=max(drink(N - 1, left - 1) + glass[N],drink(N - 1, 2));
    }
    else if (left == 0)
    {
        D[N][left]=drink(N - 1, 2);
    }
 
    return D[N][left];
}
 
int main()
{
    int n;
    cin >> n;
    memset(D, 0, sizeof(D));
    for (int i = 1; i <= n; i++)
    {
        cin >> glass[i];
    }
 
    cout << max({ drink(n, 2),drink(n,0),drink(n,1) }) << endl;
 
 
    return 0;
}