[백준/C++] 조 짜기 (No. 2229)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 문제에 대한 설명이 애매해서 추가하면, 나이로 정렬을 했기 때문에 붙어있는 사람들끼리 조를 이루어야한다는 조건이 추가되어야 한다.

 

즉, A, B, C 순서로 있다면, [A, C]로 조를 만들 수 없지만, [A, B, C]로 조를 만들 수 있다는 뜻이다.

 

이제 이를 이용해 문제를 풀어 나가면 된다.

 

만약 i번째 사람까지 조가 정해졌다면, 그때의 최대 값을 이용해 j번째 사람까지 조가 이루어졌을 경우의 최대값을 갱신해 나가면서 풀 수 있다.

 

이렇게 단계로 풀 수 있기 때문에 DP 배열을 이용해 풀 수 있다.

 

dp[i]를 i번째 사람까지 조가 정해진 경우라고 하면, i+1 ~ j번 사람이 조를 이루었을 때 최대 점수차이를 이용해

dp[j] = max(dp[j],  dp[i] + max(i+1 ~ j) - min(i+1~ j)) 로 갱신해 나가면 된다.

 

위 과정을 계속 반복해서 dp[N]에 저장된 값을 출력하면 조를 짰을 때, 최대 점수를 구할 수 있다.

 

 

 

[아이디어 정리]

1. dp[i]를 i번째 사람까지 조를 이루었을 경우의 최대 점수로 정의한다.
2. dp[j]는 dp[i] + max(i+1, j) - min(i+1, j)와 비교해 최대값을 갱신하면 된다.
3. 최종적으로 계산된 dp[N]을 출력한다.

 

 

 

Code

 

 

 

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> v(N+1,0);
    for (int i = 1; i <= N; i++) {
        cin >> v[i];
    }
    vector<int> dp(N+1, 0);// dp[i] = i번째 사람까지 조가 짜 있는 경우의 최대값
    int minV, maxV;
    for (int i = 0; i < N; i++) {
        minV = v[i+1];
        maxV = v[i+1];
        for (int j=i+1; j<=N; j++)
        {
            minV = min(minV, v[j]);
            maxV = max(maxV, v[j]);
            dp[j] = max(dp[j], dp[i] + maxV - minV);
        }
    }
    cout << dp[N];
   
    return 0;
}

 

---

 

처음에 문제가 헷갈리게 적어져 있었다...

 

조를 만들기 위해서는 사이에 있는 사람들이 전부 한 조여야한다는 조건이 추가되면 좋을 것 같다.

 

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