[코딩테스트 C++] 포도주 시식

오늘의 문제

https://www.acmicpc.net/problem/2156

포도주 시식

접근 방식

• 예전에 풀었던 계단문제랑 비슷하나 달라진 점이 있다면 건너뛸 수 있는 제한은 없다는것.
• 2개를 안먹고 지나칠 수 있다. 그러므로, i-3도 계산이 필요하다.
• dp[i-3] + num[i-1]/ dp[i-2]/ dp[i-1]의 비교가 필요하다.

나의 풀이

#include <iostream>
using namespace std;
const int MAX = 10003;
int num[MAX];
int n;

int solution(){
    int dp[MAX] ={0, };
    int answer = 0;
    for(int i=3;i<n+3;i++){
        dp[i] = max(dp[i-3] + num[i-1], dp[i-2]) + num[i];
        dp[i] = max(dp[i-1], dp[i]);
        answer = max(answer, dp[i]);
    }
    return answer;
}

int main(){
    cin>>n;
    
    for(int i=3;i<n+3;i++){
        cin>>num[i];
    }
    cout<<solution()<<endl;
    return 0;
}

다른 풀이

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[3], tmp;

int main()
{
	int n, x;
	scanf("%d", &n);
	while (n--)
	{
		scanf("%d", &x);
		tmp = max(dp[0], max(dp[1], dp[2]));
		if (dp[1]) dp[2] = dp[1] + x;
		dp[1] = dp[0] + x;
		dp[0] = tmp;
	}
	printf("%d\n", max(dp[0], max(dp[1], dp[2])));
}

배울 점

• 맞다. 3개짜리 배열만으로도 문제풀이가 가능하다!! 접근하는게 그것 뿐이므로.