[백준] 2156 포도주 시식

[백준2156] 포도주 시식

효주가 포도주 시식을 하려고 한다.
테이블 위에는 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여있다.
다음과 같은 규칙을 지켜야한다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여있는 3잔을 모두 마실수는 없다.

1부터 N까지의 번호가 붙어있는 N개의 포도주 잔이 순서대로 테이블 위에 놓여있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을때, 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

마지막 N 잔을 마셨을 때, 이전의 경우는 2가지로 생각할 수 있다.

1) 직전에 포도주(N-1잔)를 마신 경우
-> N-2잔을 고르면 연속 3잔이 되기 때문에 고를 수 없음
DP[N]=DP[N-3]+arr[N-1]+arr[N]

2) 직전에 포도주(N-1잔)를 마시지 않은 경우
->N-2잔을 고를 수 있음
DP[N]=ARR[N]+DP[N-2]

최대값을 구하는 것이므로 점화식을 계속 계산해 비교해가면 된다.
이전에 풀았던 [백준 2570]계단오르기 문제와 비슷함.

• 위의 두가지 조건 만으로는 틀렸습니다가 나옴.
  반례로, 100,400,2,1,4,200 이 주어졌을때
  위의 조건 식을 이용하면 701이 나온다.
  하지만 답은 100,400,4,200->704가 납이다.
  포도주가 2번 연속 안먹을 경우가 존재한다.

계단과 다른점은... 계단은 마지막 계단을 꼭 밟아야하는데
이 문제는 마지막을 꼭 먹지 않아도 된다는 점이다.

그러므로 DP[N]=max(DP[N-1],DP[N])이라는 점화식을 추가해줘야 한다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
long long int dp[10001];


int main() {
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
	}

	dp[1] = arr[1];
	if (N > 1) dp[2] = arr[1] + arr[2];

	for (int i = 3; i <= N; i++) {
		
		dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);
	    dp[i] = max(dp[i - 1], dp[i]);
	}

	printf("%lld", dp[N]);
	return 0;
}

그리고 위에서 dp[1],dp[2]를 초기화하는 부분에서
예전에 했던대로
for (int i = 1; i <= 3 && i <= N; i++) {
if (i != 3)
dp[i] = arr[i] + dp[i - 1];
else
dp[i] = max(arr[i - 1] + arr[i], arr[i - 2] + arr[i]);
}

를 사용하니 계속 틀리게 나왔는데..
3
3
2
1
의 반례에서 틀린 값이 나왔다.
이유는 위와 동일하다.