[백준] 2156번 포도주 시식

2156 포도주 시식

문제

---

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

---

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

---

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

---

풀이)

dp를 이용해서 푼 문제이다.

연속해서 2잔까지 마실 수 있음을 생각해서 3가지 경우로 나눠봤다.

현재 i번째 잔이라면

1. i번째 잔을 마시지 않을 경우

2. i번째 잔을 마실 경우 

  2.1. i번째 잔이 연속한 2개의 잔 중 첫번째 잔일 경우

  2.2. i번째 잔이 연속한 2개의 잔 중 두번째 잔일 경우

이를 이용해 배열을 선언을 아래와 같이 했다.

int dp[10000][3] 

//dp[i][0] = max(max(dp[i-1][0],dp[i-1][1]),dp[i-1][2))

    i번째 위치의 잔을 마시지 않겠다.

    → 마시지 않을 것이므로, 이전 i-1번째 잔의 3가지 경우 중 최대 값을 가져온다.

//dp[i][1] = dp[i-1][0] + vec[i]

    i번째 위치의 잔이 연속하는 잔에서 앞의 잔

    → 이전 i-1번째 잔의 마시지 않는 경우 값 + i번째 잔의 포도주 양

//dp[i][2] = dp[i-1][1] + vec[i]

    i번째 위치의 잔이 연속하는 잔에서 뒤의 잔

    → 이전 i-1번째 잔의 첫번째 잔의 경우 값 + i번째 잔의 포도주 양

따라서 마지막last 잔까지 배열값을 구한뒤

dp[last][0], dp[last][1], dp[last][2] 중 최대값을 출력하면 된다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n; //포도주 잔수
int vec[10000]; // 포도주 값 저장
int dp[10000][3];
 
int main() {
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &vec[i]);
    }
    //[잔 위치][0] = 이 잔을 마시지 않겠다
    //[잔 위치][1] = 이 잔이 연속하는 잔에서 앞의 잔이다
    //[잔 위치][2] = 이 잔이 연속하는 잔에서 뒤의 잔이다
    dp[0][0] = 0;
    dp[0][1] = vec[0];
    dp[0][2] = 0;
 
    //두번째 잔부터 계산시작
    for (int i = 1; i < n; i++) {
        //i번째 잔은 안마실거니깐 이전 잔의 3가지 경우중에서 최대값을 가지고 온다.
        dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1]),dp[i - 1][2]);
        //i번째 잔이 연속된 값에서 첫번째 값이니깐 i-1번째 3가지 경우중
        //i-1을 포함하지 않는 경우의 합을 가지고 온다.
        dp[i][1] = dp[i - 1][0] + vec[i];
        //i번째 잔이 연속된 값에서 두번째 값이니깐 i-1번째 3가지 경우중
        //i-1을 연속된 값중 첫번째로 가지는 경우의 합을 가지고 온다.
        dp[i][2] = dp[i - 1][1] + vec[i];
    }
 
    //포도주의 최대 합 10,000,000
    int mval = max(max(dp[n-1][0], dp[n - 1][1]), dp[n - 1][2]);
 
    printf("%d", mval);
 
    return 0;
}