[BOJ 2229] 조 짜기

- 문제 요약

 

첫째 줄에 학생의 수 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다. 이 학생들을 묶어 조를 편성하려 한다. 가급적이면 실력 차이가 많이 나도록 조를 편성해야 한다. 조의 개수는 상관이 없다.

각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

DP[x] : ~ i번 학생까지 조를 편성했을 때, 잘 짜여진 정도의 최댓값.

DP[i] = DP[j] + (1 ~ j 중 최댓값) - (1 ~ j 중 최솟값)

 

 

- 코드 작성

 

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

#define MAX 1001
int n,arr[MAX],dp[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=2;i<=n;i++){
		int mn=arr[i],mx=arr[i];
		for(int j=i-1;j>=0;j--){
			mn=min(arr[j+1],mn);
			mx=max(arr[j+1],mx);
			dp[i]=max(dp[i],dp[j]+mx-mn);
		}
	}
	cout<<dp[n];
}

코드 제출 결과