백준 2229, 조 짜기

개요

문제 링크
골드 5, DP
최댓값과 최솟값의 차이의 합이 최대가 되도록 연속부분집합을 구성하기

---

접근

1. 여러개의 집합을 구성해야 하니까 2차원 dp가 필요한가? 했는데 1차원으로 충분했음.

2. 우선 dp와 그 업데이트 부터 생각하자. dp에는 답이 될 최대 값를 저장한다. 그럼 업데이트는? 앞에서부터 보면서 최대 값 + 더해질 값이 더 큰 경우 업데이트 하면 된다. 말이 애매한데 예시를 보자.

   i	1	2	3	4	5
   a[i]	2	5	7	1	3
   dp[i]	0	3	5	9	?
   set	{2}	{2,5}	{2,5,7}	{2,5},{7,1} =3+6

   각 집합을 보면 4까지 잘 이해가 된다. 이때 i=5라고 하자. 5일때는 i=1부터 4까지 비교를 한다.

3. 어떻게 비교하냐? 하면 이렇게 생각해보자

    // i=1과 비교
    {2} + {5,7,1,3} = 0+6 = 6
    // i=2와 비교
    {2,5} + {7,1,3} = 3+6 = 9
    // i=3과 비교
    {2,5,7} + {1,3} = 5+2 = 7
    // i=4와 비교
    {2,5},{7,1} + {3} = (3+6)+0 = 9

   비교할 부분의 오른쪽 집합을 나누지 않고 더해주면서 값이 최대가 되는 경우를 찾는다. 그럼 {2,5},{7,1,3}으로 나눈 경우가 최대임을 알 수 있고, 집합의 개수 제한이 없으므로 1차원 dp로 업데이트 해주면 된다.

4. 나는 비교할 부분의 오른쪽 집합의 최대-최소를 미리 저장해서 사용했다. 혹시나 O(n^4) 되면서 시간초과 뜰까봐

---

Pseudo code

for (i = 0~n)
    for(j = 0~i-1)
        update = dp[j] + max(j,i) - min(j,i)
        if (dp[i] < update)
            dp[i] = update

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];

    int val[n+1][n+1];
    for (int i=0; i<=n; i++)
        for (int j=0; j<=n; j++)
            val[i][j] = 0;

    int p, q;
    for (int i=1; i<=n; i++) {
        p = a[i], q = a[i];
        for (int j=i+1; j<=n; j++) {
            p = max(p, a[j]);
            q = min(q, a[j]);
            val[i][j] = p-q;
        }
    }

    int dp[n+1];
    dp[0] = 0;
    for (int i=1; i<=n; i++) {
        dp[i] = 0;
        for (int j=0; j<i; j++)
            dp[i] = max(dp[i], dp[j]+val[j+1][i]);
    }
    cout << dp[n];
}