백준 2156번 [포도주 시식] (C++) -yes6686- 티스토리

백준 문제 풀이: 2156 [포도주 시식]

---

문제 링크: https://www.acmicpc.net/problem/2156

문제 설명:

여러 잔의 포도주가 일렬로 나열되어 있고, 포도주를 마시는 규칙은 다음과 같습니다:

• 포도주는 연속으로 세 잔을 마실 수 없습니다.
• 각 포도주의 양이 주어질 때, 최대한 많은 양의 포도주를 마실 수 있는 값을 구합니다.

---

문제 해결 코드

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

int arr[10001]; // 각 포도주의 양
int dp[10001];  // i번째 포도주까지 최대 마실 수 있는 포도주의 양

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 포도주 잔의 개수
    cin >> n;

    // 포도주 양 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 초기값 설정
    dp[0] = arr[0];
    dp[1] = arr[0] + arr[1];
    dp[2] = max({arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2]});

    // 동적 프로그래밍으로 최대 마실 수 있는 포도주 양 계산
    for (int i = 3; i < n; i++) {
        dp[i] = max(dp[i - 1],                // 현재 포도주를 마시지 않는 경우
                    max(arr[i] + dp[i - 2],   // i번째 포도주를 마시고 i-2번째까지 마시는 경우
                        arr[i] + arr[i - 1] + dp[i - 3])); // i와 i-1번째 포도주를 마시는 경우
    }

    // 결과 출력
    cout << *max_element(dp, dp + n) << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 현재 포도주를 마시는 경우와 마시지 않는 경우를 비교하며 최댓값을 구합니다.
• 구현 세부사항:
  • dp[i]: i번째 포도주까지 마셨을 때 최대 마실 수 있는 포도주의 양
  • 점화식:
    • dp[i] = max(dp[i-1], arr[i] + dp[i-2], arr[i] + arr[i-1] + dp[i-3])
  • 초기값:
    • dp[0] = arr[0]: 첫 번째 포도주를 마신 경우
    • dp[1] = arr[0] + arr[1]: 첫 번째와 두 번째 포도주를 마신 경우
    • dp[2] = max(arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2]): 세 잔 중 최댓값
• 시간 복잡도 분석: O(n)
  • 각 포도주 잔에 대해 상수 시간 연산을 수행합니다.

---

결과

포도주를 마시는 규칙을 준수하면서 최대로 마실 수 있는 포도주의 양을 정확히 계산합니다. 동적 프로그래밍을 활용하여 효율적으로 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!