[C++] 2156 포도주 시식

👉 2156 포도주 시식

[정답 코드]

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n, i;
    int podo[10000] = {0};
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> podo[i]; 
    }
    int memo[10000][3] = {{0, 0, 0}};
    memo[0][1] = podo[0];
    for (i = 1; i < n; i++) {
        memo[i][0] = *max_element(memo[i - 1], memo[i - 1] + 3);
        memo[i][1] = memo[i - 1][0] + podo[i];
        memo[i][2] = memo[i - 1][1] + podo[i];
    }
    cout << *max_element(memo[n - 1], memo[n - 1] + 3) << endl;
    return 0;
}

[풀이]

문제의 조건(포도주를 연속 3잔 마실 수 없다)에 맞추어 3 * 10000 배열로 메모이제이션을 진행했다.

• 첫 번째 열은 n번째 포도주를 마시지 않을 때의 최댓값을 의미한다. 즉, 전 항까지의 값 중 최댓값을 넣으면 된다.
  *max_element(memo[i - 1], memo[i - 1] + 3)
• 두 번째 열은 n번째 포도주를 마시는 데, 이 잔이 연속 1번째 잔일 때를 의미한다.
  memo[i - 1][0] + podo[i]
• 세 번째 열은 n번째 포도주를 마시는 데, 이 잔이 연속 2번째 잔일 때를 의미한다.
  memo[i - 1][1] + podo[i]

✔ max_elemnt()

• <>
• 구간(array, list, vector 등) 안에서 최댓값을 구한다.
• 해당하는 값의 주소 반환
• 모든 STL 컨테이너에서 선형 동작한다. 시간 복잡도 = O(N)

참조 및 예시

[적용 자료구조 및 알고리즘]

• Dynamic Programming