문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 디피로 풀 수 있는 문제이다.
  • 앞서 푼 2579번 계단 오르기 문제와 유사하다.
  • 연속으로 3잔을 마실 수 없다는 것을 위해 바로 전과 두 칸 전에서 왔을 때의 최대값을 저장하여 업데이트 한다.

유의할 점

  • 계단 오르기와 다르게 두칸을 띄는 것 말고도 세칸, 네칸도 뛸 수 있다는 사실을 기억하기 바란다.
  • 그리고 꼭 마지막 지점을 지나지 않아도 된다.
  • 반례는 [9, 8, 0, 0, 1, 2], 20 이다.

코드

#include <cstdio>
#include <vector>
using namespace std;

int n, wine[10003], taste[10003][2];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)scanf("%d", &wine[i]);
    taste[0][1] = wine[0], taste[1][1] = wine[1];
    for(int i = 0; i <= n; i++){
        taste[i+1][1] = max(taste[i+1][1], max(taste[i][0], taste[i][1]));
        taste[i+2][0] = max(taste[i+2][0], max(taste[i][0], taste[i][0]));

        if(taste[i+2][0] < taste[i][0] + wine[i+2])taste[i+2][0] = taste[i][0] + wine[i+2];
        if(taste[i+2][1] < taste[i][0] + wine[i+2])taste[i+2][1] = taste[i][0] + wine[i+2];

        if(taste[i+2][1] < taste[i][1] + wine[i+2])taste[i+2][1] = taste[i][1] + wine[i+2];
        if(taste[i+2][0] < taste[i][1] + wine[i+2])taste[i+2][0] = taste[i][1] + wine[i+2]; 
        
        if(taste[i+1][0] < taste[i][1] + wine[i+1])taste[i+1][0] = taste[i][1] + wine[i+1];
    }
    printf("%d", max(taste[n][0], taste[n][1]));
}

느낀점

  • 계단 오르기 코드에 갇혀서 반례를 발생시켰었다.
  • 문제를 제대로 이해하는 연습을 하자!