백준 2229번 : 조 짜기

  혼자 생각해서 풀었더니 시간에 야무지게 초과해버려서 슬퍼하면서 검색을 했다. 와 역시 검색이 짱이야... 검색해서 나온 코드를 보고 내 방식대로 더 깔끔하게 수정해서 제출했다. 내가 참고한 블로그는 4ms였는데 나는 0ms 나왔으니까 내가 더 깔끔함! 암튼 그럼!

---

  풀이

  n개의 숫자가 주어졌을 때 적당히 그룹을 짓고 그룹 내에서 최대 최소의 차를 구한 것이 그룹의 점수이며 그룹 점수를 모두 더한 것이 dp의 정의다.

 

dp[n] : n번째 숫자까지 최대 그룹 합

 

  마지막 숫자인 n번째 숫자가 포함된 그룹의 첫 번째 숫자가 전체 수열 중 j번째 숫자라고 하자. 이때 j는 최대 n이고 최소 1이다. 이때 dp [n]은 다음과 같이 계산할 수 있다.

 

dp [n] = 그룹 점수 + dp [j-1]

 

  그룹은 j번째 수부터 n번째 수이기 때문에 해당 그룹에서 최대와 최소의 차를 계산해주면 된다.

 

#include <iostream>

using namespace std;

int n;
int seq[1002];
int dp[1002];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> seq[i];
    }
        
    for(int i = 2; i <= n; i++)
    {
        int low = 10004;
        int high = -1;
        
        for(int j = i; j >= 1; j--)
        {
            low = min(low, seq[j]);
            high = max(high, seq[j]);
            dp[i] = max(dp[i], high - low + dp[j-1]);
        }
    }
    
    cout << dp[n];
    
    return 0;
}