[BOJ] 2156. 포도주 시식(DP)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

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

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

1. 상태 정의

- DP[N]는 N번째 잔까지 있을 경우 마실 수 있는 최대 포도주

2. 점화식

- 점화식을 세우기 위해서 N번째 잔의 상태를 먼저 나눠줘야 한다.

N번째 잔은 3가지 경우로 나뉠 수 있다.

Case 1. N번째 잔을 마시지 않을 경우,

Case 2. N번째 잔이 연속 1번째 잔일 경우

Case 3. N번째 잔이 연속 2번째 잔일 경우

이 3가지 경우 해의 최댓값이 DP[N]이 된다.

입력 A[]와 DP[]의 결과는 아래 그림과 같다.

N이 3일 경우를 보자.

Case 1. N(3)번째 잔을 마시지 않을 경우, 

(N-1(2)번째 잔까지 있을 경우 마실 수 있는 최대 포도주)

DP[N] = DP[N-1]

DP[3] = DP[2] 

Case 2. N(3)번째 잔이 연속 1번째 잔일 경우, 

(N-1(1)번째 잔까지 있을 경우 마실 수 있는 최대 포도주에 현재 잔을 더함)

DP[N] = DP[N-2] + A[N]

DP[3] = DP[1] + A[3]

Case 3. N(3)번째 잔이 연속 2번째 잔일 경우,

(N-3(0)번째 잔까지 있을 경우 마실 수 있는 최대 포도주에 이전 잔과 현재 잔을 더함)

DP[N] = DP[N-3] + A[N-1] + A[N]

DP[3] = DP[0] + A[2] + A[3]

다음 동작들도 위와 동일하게 동작한다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <cstdio> #include <algorithm> using namespace std;   int A[10001], DP[10001];   int main(void) {     int n, i;     freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++)         scanf("%d", &A[i]);       DP[1] = A[1], DP[2] = A[1] + A[2];     for (i = 3; i <= n; i++)          DP[i] = max(max(DP[i - 1], DP[i - 2] + A[i]), DP[i - 3] + A[i - 1] + A[i]);          printf("%d\n", DP[n]);       return 0; } Colored by Color Scripter

cs

line 15) 직관적인 문제에 대한 해를 먼저 구해준다.

line 17) 점화식 적용!!