[백준/C++] 2156 포도주 시식 (S1)

 

유형	난이도	완료일	링크	특이사항
DP	실버1	23/02/25	https://www.acmicpc.net/problem/2156

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10000];
int sum[3][10000];

int main(void)
{
	int n;
	cin >> n;
	

	for(int i = 0; i< n; i++)
	{
		cin >> arr[i];
	}
	
	sum[0][0] = arr[0]; //이어짐
	sum[1][0] = arr[0]; //한 칸 뜀
	sum[2][0] = arr[0]; // 두 칸 뜀
	
	if(n > 1)
	{
		sum[0][1] = arr[0] +arr[1];
		sum[1][1] = arr[1];
		sum[2][1] = arr[1];
	}
	
	if(n > 2)
	{
		sum[0][2] = arr[1]+arr[2];
		sum[1][2] = arr[0]+arr[2];
		sum[2][2] = arr[0]+arr[2];	
	}
	
	if(n > 3)
	{
		sum[0][3] = sum[1][2] + arr[3];
		sum[1][3] = sum[0][1] + arr[3];
		sum[2][3] = sum[0][1] + arr[3];
	}
		
	if(n > 4)
	{
		sum[0][4] =	arr[0] + arr[1] + arr[3] + arr[4];
		sum[1][4] = max(sum[0][2], sum[1][2]) + arr[4];
		sum[2][4] = arr[0] + arr[1] + arr[4];	
	}
		
	for(int i = 5; i<n; i++)
	{
		sum[0][i] = arr[i] + max(sum[1][i-1], sum[2][i-1]);
		sum[1][i] = arr[i] + max(max(sum[1][i-2],sum[2][i-2]), sum[0][i-2]);
		sum[2][i] = arr[i] + max(max(sum[1][i-3],sum[2][i-3]), sum[0][i-3]);
	}
	
	int max = 0; 
	int temp = 0;
	
	temp = sum[0][n-1];
	if(temp > max)
		max = temp;
	temp = sum[1][n-1];
	if(temp > max)
		max = temp;
	temp = sum[2][n-1];
	if(temp > max)
		max = temp;
	temp = sum[0][n-2];
	if(temp > max)
		max = temp;
	temp = sum[1][n-2];
	if(temp > max)
		max = temp;	
	temp = sum[2][n-2];
	if(temp > max)
		max = temp;	
	
	cout << max;
}

2579 계단 오르기와 비슷한 문제였다. 계단 오르기는 진행 방향이 주어지고 2칸 이상 뛰어넘을 수 없다는 제약이 존재하지만 이 문제에서는 그런 제약이 없다. 그래서 처음엔 2칸을 건너뛰어야 하는 경우가 있다는 것을 생각하지 못하고 풀어서 계속 틀렸었다.

예를 들어 100 100 1 1 100 100 → 이렇게 수가 주어지면, 양 옆의 100을 취하기 위해서 가운데 1 1 을 포기해야 한다. 따라서 n번째 포도주 잔을 선택하는 경우의 수는 세 가지로 나뉜다. 첫 째는 n-1과 연속하는 것(이 경우 n-1은 n-2과 떨어져 있어야 한다), 둘 째는 n-1을 건너뛰고 n-2가 선택된 것, 셋 째로 n-3이 선택 되고 n-1과 n-2 모두 선택되지 않은 것이다. 각 경우에 따른 최댓값을 누적해가며 저장해두면 마지막 n-1번째와 n번째 포도잔 선택시의 누적 합 중에서 가장 큰 값이 정답이 된다. n-1 또는 n은 무조건 선택될 수 밖에 없기 때문이다.(n-1,n-2 모두 선택 안하는 경우가 최댓값일 수 없다. 놓치는 것 없이 추가만 되기 때문에)

n=1~4인 경우들 까지는 for문의 규칙과 다르게 값이 정해지므로 하나씩 직접 할당해주었고 n=5이상부터는 for문으로 값을 할당하였다. 세 가지 경우마다 선택될 수 있는 후보가 여럿 있어서 for문을 짜는게 꽤 헷갈렸다.

더 간결한 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
    int n; cin >> n;
    int a[10001]={0};
    int dp[10001]={0};
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    dp[0] = 0;
    dp[1] = a[1];
    dp[2] = a[1] + a[2];
    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-1]});
    }
    printf("%d\\n", dp[n]);
}

dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});

이 점화식으로 내 코드처럼 310000의 배열이 아니라 110000의 배열만으로 문제를 해결할 수 있었다.

다른 풀이를 보니 나도 방법이 있을 것 같았는데 더 생각해보지 않고 그냥 무식하게 구현한 것이 아쉽다.

핵심은, 난 n번째 칸을 생각할 때 n번째 칸을 무조건 선택한 경우로 생각했는데, 꼭 n번째의 포도주를 선택할 필요 없이 그냥 ‘n번째 까지의 최대 합’을 저장한다는 생각의 차이인 것 같다. 결국 n번째 까지의 합의 경우의 수는 마찬가지로 세 가지이고 그 중 가장 큰 값을 누적해가며 저장하는 것을 반복하면 된다.