[백준 BOJ][DP] 2156 포도주 시식

2156_포도주 시식

 

링크

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

 

풀이1

 

 

A[i]를 i번째 포도주의 양, DP[N][L]을 N번째 마신 포도주의 양, 연속 L번째라고 정의하겠습니다.

 

 

 

우선 i번째에 0번 연속으로 먹는다(이번에 먹지 않는다)고 했을 때,

DP[i][0]을 정의할 수 있습니다.

이번에 먹지 않으니 변화가 없다는 뜻입니다. 그리고 전에 먹었는지 먹지 않았는지는 상관하지 않기 때문에 전 단계에서 먹은 양 중에 최대로 먹은 양을 가져오면 됩니다.

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

 

1번 연속으로 먹는다(이번에 먹고 전 단계에서 먹지 않았다)고 했을 때,

DP[i][1]을 정의할 수 있습니다.

이번에 먹으니 A[i]를 더해줘야 합니다. 그리고 전에 먹지 않았어야 이번이 1번 연속으로 먹는 것이기 때문에 DP[i-1][0]을 가져와야 합니다.

DP[i][1] = DP[i-1][0] + A[i]

 

2번 연속으로 먹는다(이번에 먹고 전 단계에서 먹었다)고 했을 때,

DP[i][2]를 정의할 수 있습니다.

이번에 먹으니 A[i]를 더해줘야 합니다. 그리고 전에 먹었어야 이번에 2번 연속으로 먹는 것이기 때문에 DP[i-1][1]을 가져와야 합니다.

DP[i][2] = DP[i-1][1] + A[i]

 

 

마지막은 max(DP[n][0], DP[n][1], DP[n][2])를 출력해주면 됩니다.

 

 

코드1

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

//2156_포도주 시식_1 #include <iostream> #include <algorithm> using namespace std;   int DP[10001][3]; int A[10001];   int main() {     int n, MAX;          cin >> n;       for (int i = 1; i <= n; ++i)         cin >> A[i];       for (int i = 1; i <= n; ++i) {         DP[i][0] = max(DP[i - 1][0], DP[i - 1][1]);         DP[i][0] = max(DP[i][0], DP[i - 1][2]);         DP[i][1] = DP[i - 1][0] + A[i];         DP[i][2] = DP[i - 1][1] + A[i];     }       MAX = max(DP[n][0], DP[n][1]);     MAX = max(MAX, DP[n][2]);       cout << MAX << endl;       return 0; } Colored by Color Scripter

cs

 

 

 

풀이2

 

A[i]를 i번째 포도주의 양이라고 정의하고, DP[N]을 N번째 포도주를 최대로 마신 양이라고 정의합니다.

 

0번 연속으로 먹을 때, 먹지 않는 것과 다름 없으니 DP[N] = DP[N-1]입니다.

1번 연속으로 먹을 때, 전 단계에서 먹지 않았으니 전전 단계에 A[N]를 더하면 됩니다.

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

2번 연속으로 먹을 때, 전 단계에서 먹었고, 전전 단계에서 먹지 않았으니, 전전전 단계에 A[N-1]과 A[N]을 더하면 됩니다.

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

 

위에 나온 식 3개 중에 가장 큰 값을 DP[N]에 넣어주면 되겠죠?

 

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

마지막에는 DP[N]을 출력해주면 됩니다.

 

코드2

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

//2156_포도주 시식2 #include <iostream> #include <algorithm> using namespace std;   int DP[10001]; int A[10001];   int main() {     int n;       cin >> n;       for (int i = 1; i <= n; ++i) {         cin >> A[i];     }       DP[1] = A[1];       for (int i = 2; i <= n; ++i) {         DP[i] = max(DP[i - 1], DP[i - 2] + A[i]);         DP[i] = max(DP[i], DP[i - 3] + A[i - 1] + A[i]);     }       cout << DP[n] << endl;       return 0; } Colored by Color Scripter

cs