백준 BOJ 2229 - 조 짜기

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

2229번: 조 짜기

 

DP 사용해서 해결한 문제.

dp[k] : k명까지 조를 짰을때 잘 짜여진 정도의 최댓값 으로 정의한다.

 

또한, 인덱스 s부터 e까지의 사람들로

조를 편성했을때 조가 잘 짜여진 정도를 O(N) 에 구해내는 함수를

하나 작성하고, (for문을 통해 만들면 된다)

이를 cal(s,e)라고 정의한다.

 

dp[1]은 당연히 0이 될 것이고,

$k$보다 작거나 같은 수 $a$에 대해서

dp[a-1] + cal(a,k) 은 기존 $a-1$ 명까지 조를 짰을때의 최대값과

남은 사람들끼리 하나의 조를 짰을때의 합이므로,

 

모든 탐색 가능한 a에 대해서 계산해준다음 그 최댓값을 dp[k]로 갱신해주면

정답을 받을 수 있다.

전체 시간복잡도는 O(N^2).

 

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

int arr[12345] = {0};
int dp[12345] = {0}; // dp[i] - i명까지 조를 짰을때 잘짜여진 정도의 최댓값. 

int cal(int s, int e){
	int mx=0,mn=998244353;
	for(int i=s; i<=e; i++){
		mx = max(mx, arr[i]);
		mn = min(mn, arr[i]);
	}
	return mx-mn;
}

int main(){
	int N;
	cin >> N;
	
	for(int i=1; i<=N; i++) cin >> arr[i];
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=i; j++){
			dp[i] = max(dp[i], dp[j-1] + cal(j,i));
		}
	}
	
	cout << dp[N];
	return 0;
}