[Baekjoon] 백준 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 이하의 음이 아닌 정수이다.

출력

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

예제

6
6
10
13
9
8
1

출력
33

코드

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

int a[10001];
int d[10001][3];
int dp[10001];

//일차원배열 사용
int main() {
    int n;
    cin >> n;

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

    cout << dp[n] << endl;
    return 0;
}
// 이차원배열 사용
int main() {
    int n; 
    cin >> n;
    for (int i =1; i <= n; i++) {
        cin >> a[i];
    }
    d[0][0] = 0;
    d[0][1] = 0;
    d[0][2] = 0;
    for (int i = 1; i <= n; i++) {
        d[i][0] = max(d[i-1][0], max(d[i - 1][1], d[i - 1][2]));
        d[i][1] = d[i - 1][0] + a[i];
        d[i][2] = d[i - 1][1] + a[i];
    }

    cout << max(max(d[n][0], d[n][1]),d[n][2]) << '\n';
    return 0;
}

해결방법

이차원배열 사용

• 포도주자 N잔 있을 때 N에서 세 가지 방법을 고려해야한다.
  1. N번째 포도주를 먹지 않는경우.
  2. N번째 포도주를 먹었을 때 1번 연속이 되는 경우.
  3. N번째 포도주를 먹었을 때 2번 연속이 되는 경우.
• d[i][j]는 i번째 잔을 j번 연속으로 먹었을 때의 마신 포도주의 양이다.
• 포도주를 먹지 않는 경우는 i-1번째에서 나오는 세 가지 경우들 중 최대값과 동일한 값을 가지면 된다.

    d[i][0] = max(d[i-1][0], max(d[i - 1][1], d[i - 1][2]));

• 포도주를 마셨을 때 1번 연속이 되기 위해서는 i-1번째에서 포도주를 마시지 않고 i번째만 마셔야한다.

    d[i][1] = d[i - 1][0] + a[i];

• 마지막 경우는 i-1번째에서 한 번 마신 경우이다.

    d[i][2] = d[i - 1][1] + a[i];

• 출력할 때는 n번째에서 3가지 경우 중 최대값을 반환한다.

    cout << max(max(d[n][0], d[n][1]),d[n][2]) << '\n';

일차원배열 사용

• 이차원 배열과 같이 세 가지 경우를 모두 고려해야한다.
• d[n]은 n번째 잔을 마셨을 때의 최대값을 갖고있다.
• 포도주를 먹지 않는 경우는 d[i-1]번째와 같은 값을 가진다. d[i] = d[i-1]
• 1잔 연속으로 마시는 경우는 d[i-2]번째의 최대값과 현재 잔을 마신 경우를 더한다.
  d[i-2] + a[i]
• 2잔 연속으로 마시는 경우 d[i-3]번째의 최대값과 i-1번째와 현재 잔을 마신 경우를 더한다. d[i-3] + a[i-1]+ a[i]

각주

• 일차원 배열에서 d는 세 가지 경우에 대해 나올 수 있는 값의 최대값을 항상 저장하고 있다. 따라서 2잔 연속으로 마시는 경우는 a[i-1] + a[i]의 값과 그 이전까지 누적된 양을 더해야한다. 이 때 d[i-2]는 a[i-2]를 마셨을 때의 최대값을 저장하고 있으니 d[i-3]을 찾아서 더해주게된다.