BOJ 12909 그래프 만들기

BOJ 12909 그래프 만들기

[분류 : 다이나믹 프로그래밍]

 

[풀이]

  [노드의 수] 현재 노드 u에서 자식 노드를 추가하는 행위는 전체 사용할 수 노드 수가 줄어든다. 단 그 자식 노드를 루트로 하는 서브 트리의 크기(노드의 수)를 결정해줘야 한다. 당연한 소리지만 현재 N을 사용할 수 있다면 서브 트리의 크기는 최대 N-1다.

 

  [상태] 서브트리의 크기가 x라고 하자. 그러면 현재 노드 u에서 추가적으로 사용할 수 있는 노드 수는 N - x가 된다. 자식을 이미 하나 추가했으니 차수는 하나 증가한다. 결국 상태는 (노드 수, 차수)로 볼 수 있다. 노드의 수는 계속 줄어들 수 밖에 없으므로 이 상태를 유지하며 부분 문제를 해결, 부분 구조를 사용해주시면 되겠다.

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 52;
int score[MAX_N], dp[MAX_N][MAX_N];
int rec(int n, int d) {
	if (n == 1) return score[d];
	int& ret = dp[n][d];
	if (ret != -1) return ret;
	ret = score[d + n - 1];
	for (int i = 1; i < n; i++)
		ret = max(ret, rec(i, 1) + rec(n - i, d + 1));
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &score[i]);
	printf("%d", rec(N, 0));
	return 0;
}