백준 알고리즘, 2156 문제

---

풀이

2번 규칙을 보자.

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

이 말은 다음과 같은 것은 가능하다는 것이다.

1. 안마신다.

2. 1 번 연속 마신다.

3. 2 번 연속 마신다.

그리고 DP 배열은 다음과 같이 구성한다.

DP[포도잔의 수] = 정답

그렇다면 이 예제의 경우에서

6 10 만이 입력된다면

DP[2] = 16 이다.

만약 6 , 10 , 13 만이 입력된다면

DP[3] = 23 이다. 

여기에서 알 수 있는 것은 포도주 3 잔의 최대값을 알려면 3개의 값을 비교해야 한다는 것이다.

DP[3] = max ( 6 + 10 , 10 + 13 , 6 + 13 ) = 23

이 식은 또 이렇게 바꿀 수 있다.

DP[3] = max ( DP[2] ,  arr[2] + arr[3] , DP[1] + arr[3] )

위 계산이 성립되기 위해서는 먼저

arr[0] 과 DP[0] 을 초기화 해놓아야 한다.

그러면 최종적으로 다음과 같이 표현이 된다.

DP[N] = max ( DP[N - 1] ,  DP[N - 3] + arr[N - 1] + arr[N] , DP[N - 2] + arr[N] )

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/2156
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 01
 */
#include <iostream>
using namespace std;
int max(int a, int b, int c) {
    return (a > b) ? ( (a > c) ? (a) : (c) ) : ( (b > c) ? (b) : (c) );
}
int main() {
    int DP[10001] = { 0, };
    int arr[10001] = { 0, };
    int T;
    int i;
    cin >> T;
    for ( i = 1; i <= T; i++) cin >> arr[i];
    DP[1] = arr[1];
    DP[2] = arr[1] + arr[2];
    for(i = 3; i <= T; i++) {
        DP[i] = max(DP[i - 1], DP[i - 3] + arr[i - 1] + arr[i], DP[i - 2] + arr[i]);
    }
    cout << DP[T] << endl;
    return 0;
}