[백준] 2156 - 포도주 시식 (C++)

https://www.acmicpc.net/problem/2156

테이블 위에 n개의 포도주 잔이 일렬로 놓여 있고, 포도주를 시식하는 데엔 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에 원래 위치에 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수 없다.

각 포도주의 양이 주어졌을 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ n ≤ 10,000
• 0 ≤ 포도주의 양 ≤ 1,000

 

n개의 포도주 잔의 양을 저장할 배열과 각 포도주 잔을 선택하거나 선택하지 않았을 때 마실 수 있는 최대 양을 저장할 dp 배열을 선언해야 한다. 포도주 양의 최댓값은 10,000 × 1,000으로 int 범위 안에서 해결할 수 있다.

 

포도주 잔을 일렬로 확인하면서 포도주 잔을 선택하거나 선택하지 않는 것 둘 중 하나를 골라야 한다.

 

예를 들어 포도주 잔의 양이 10 20 10 0 30일 때, 포도주가 들지 않은 잔은 선택하지 않는 게 더 이득을 볼 수 있다. 포도주가 조금이라도 들어 있다면 dp[i-2]에 현재 포도주의 양을 더한 값과 dp[i-3]에 직전 포도주의 양과 현재 포도주의 양을 더한 값을 비교해서 더 큰 값을 저장하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. n 입력받기
2. 1번째와 2번째 포도주의 양 입력받고 dp 배열에 갱신하기
3. 3번째부터 n번째까지 포도주의 양을 입력받으면서 dp 배열 값 갱신하기
4. dp 배열에서 가장 큰 값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n,x[10001],dp[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    cin >> x[0] >> x[1];
    dp[0] = x[0];
    dp[1] = x[0] + x[1];
    for (int i=2; i<n; i++) {
        cin >> x[i];
        dp[i] = max({dp[i-1],dp[i-2]+x[i],dp[i-3]+x[i-1]+x[i]});
    }

    cout << *max_element(dp,dp+n+1);
}