Karatus::[2156번] 포도주 시식

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고

www.acmicpc.net

[해당 포스팅]과 완전히 같습니다.

달라 보이신다고요? 아닙니다. 잘 살펴봅시다.

위의 포스팅에서 소개된 문제는 "계단 오르기" 문제인데요. 두 문제의 조건 차이는 단 하나입니다.

"맨 마지막 index를 선택하냐 안 하냐"입니다.

즉 이 문제에서는 현재의 스텝을 굳이 밟지 않아도 된다는 것입니다.

그러므로 현재의 포도주 잔을 선택하지 않아도 되므로 최댓값을 선택할 때에 자신을 포함하지 않은 조건을 포함해야 합니다. 즉 바로 이전 DP값도 최댓값 검사에 포함시켜주어야 합니다.

[소스 보기]

티스토리툴바