[BOJ/백준][Gold5] 2229 : 조 짜기 (C++)

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

2229번: 조 짜기

 

 

[난이도] Gold5
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 해결 할 수 있습니다.

DP[i] : i번 학생까지 조에 포함시켰을 때, 조가 잘 짜여진 정도의 최댓값

위와 같이 정의하면 점화식은 다음과 같습니다.
DP[i] = DP[j] + maxv:(1~j 중 최댓값) - minv:(1~j 중 최솟값) (0<=j<=i-1)

i번 학생을 1~i 번 학생이 있는 조, 2~i번 학생이 있는 조, ... i~i번 학생이 있는 조 (조에 i번 혼자인 경우)
에 포함시켜 보면서 그 중 최댓값을 DP[i]로 업데이트 하는 방식입니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,dp[1001],a[1001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=2;i<=N;i++){
        int minv=a[i],maxv=a[i];
        for(int j=i-1;j>=0;j--){
            maxv=max(a[j+1],maxv);
            minv=min(a[j+1],minv);
            dp[i] = max(dp[i],dp[j]+maxv-minv);
        }
    }
    printf("%d",dp[N]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2229.cpp