[2156] 포도주 시식, c++

[2156] 포도주 시식

 

​

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

2156번: 포도주 시식

한줄 후기 : 후에 이 문제는 알고리즘 수업 과제로..

 

사실 계단 오르기랑 비슷해 보여서 풀었는데 좀 다르더라 그래서 좀 헤맸음.

#include <iostream>
using namespace std;
int main(){
	int n;
	int arr[10000];
	int dp[10000];
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	dp[0] = arr[0];
	dp[1] = max(arr[0]+arr[1], arr[1]);
	dp[2] = max(arr[0]+arr[1],max(arr[2],max(arr[0]+arr[2], arr[1]+arr[2])));
	
	for(int i=3; i<n; i++){
		dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
		if(dp[i]<dp[i-1])	dp[i] = dp[i-1];
		if(dp[i]<dp[i-2])	dp[i] = dp[i-2];
	}
	printf("%d",dp[n-1]);
	return 0;
}

계단 오르기랑 다른 이유는 계단 오르기는 무조건 마지막 칸을 밟는다. 근데 포도주 시식은 현재 포도주를 안먹어도 상관이 없다. 그래서 그 경우를 또 생각해 줘야함 ㅋ

​

dp 초기값이 중요한데

dp[0] = arr[0];
	dp[1] = max(arr[0]+arr[1], arr[1]);
	dp[2] = max(arr[0]+arr[1],max(arr[2],max(arr[0]+arr[2], arr[1]+arr[2])));

dp[2] 는 바로 전 포도주와 전전 포도주를 먹고 현재 포도주를 안먹는 경우, 현재 포도주만 먹는 경우, 첫번째 포도주 먹고 건너 뛰어서 현재 포도주 먹는 경우, 첫번째 포도주 건너뛰고 두번째 , 현재 포도주 연달아 먹는 경우로 초기화 해줘야 한다.

처음에 초기화에서 모든 경우로 안해서 틀렸음.

그리고 반복문 안에서도 현재 포도주를 안먹는 경우를 생각해 줘야 한다.

흠 너무 어려워 갈 길이 멀다.

​