2156번 : 포도주 시식
약간 복잡한 dp테이블을 세워야 하지만 2579번 계단 오르기와 많이 비슷하다.
dp를 세울 때 i번째에 자신이 포함될 때와 포함되지 않을 때 두가지의 경우를 생각해 주면 된다. 왜냐하면 i+1, i+2에서 i번째를 포함 할지 안할지 모르기 때문이다.
dp[i][j]는 i번째에 j가 0이면 i번째를 포함하지 않는 것, 1이면 i번째를 포함하는것을 의미한다.
그렇다면 어떻게 해야할까?
우선 dp[1][0]과 dp[1][1]은 각각 0과 arr[1]로 초기화한다.
i번째에 자신이 포함되지 않을 때는 dp[i-1][0]과 dp[i-1][1]을 비교(i-1번째 수를 포함시키는 경우와 포함시키지 않는 경우를 비교)해서 더 큰값을 이용한다.
i번째에 자신을 포함할 때는 조금 복잡해진다. 연속해서 3번을 뽑을 수 없으니 이 경우를 생각해주어야 한다.
그럼 연속해서 3번을 뽑는 것을 어떻게 알 수 있을까?
우선 i번째를 포함하는 dp를 dp[i][1] = MAX(dp[i - 1][0], dp[i - 1][1]) + arr[i]; 이렇게 채워주고 시작한다.
i를 포함하여 3번 연속이니 i-3번째는 포함되지 않으면서 i-2, i-1, i번째가 포함된다는 소리다.
즉 dp[i][1]이 dp[i-3][0] + arr[i-2] + arr[i-1] + arr[i]가 되는 순간이 3번 연달아 포함한 경우이다.
위 조건을 만족하면 dp[i][1]을 바꾸어줘야한다.
이것은 두가지 경우로 판단할 수 있다. 1) i-2번째를 포함하지 않는 경우, 그리고 2) i-1번째를 포함하지 않는 경우.
1) i-2번째를 포함하지 않고 i-1번째와 i번째를 포함할 때는 dp[i-2][0] + arr[i-1] + arr[i]의 식이 만들어진다.
2) i-1번째를 포함하지 않고 i번째를 포함할 때는 dp[i-1][0] + arr[i]의 식이 만들어진다.
1)과 2) 중 더 큰수를 택한 것이 dp[i][1]이 된다.
출력을 할 때는 N번째 포도주를 선택할 때와 선택하지 않을 때 중 더 큰값으로 출력하면 된다. 즉 dp[N][0]과 dp[N][1] 중 더 큰값을 출력하면 된다.