본문 바로가기

algorithm

dp-우수마을

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

 

1949번: 우수 마을

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며,

www.acmicpc.net

문제 유형은 트리 dp에 속한다. 

문제 조건은 다음과 같은데, 

 

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

매우 흥미롭게도 3번 조건은 필요가 없다. 왜냐하면, 1번에서 주민의 수의 총 합을 최대로 하는 과정에서 3번 조건이 알아서 충족이 되기 때문이라고 한다. 완벽하게 이해가 되지는 않지만 그렇다고 한다.


 

코드 : 

#include <iostream>
#include <vector>
#include <cstring>
//우수마을
using namespace std;
int N;
int dp[10010][2];
int A[10010];
vector<int> v[10010];
int dfs(int x,int k,int par){
	if(dp[x][k]!=-1) return dp[x][k];
	if(k==1)dp[x][1]=A[x];
	else dp[x][0]=0;
	for(int i:v[x]){
	if(i==par) continue;
	if(k==1) dp[x][1]+=dfs(i,0,x);
	else dp[x][0]+=max(dfs(i,0,x),dfs(i,1,x));
	}
//	cout<<x<<" "<<k<<" "<<dp[x][k]<<'\n';
	return dp[x][k];
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++) cin>>A[i];
	for(int i=1,u,x;i<N;i++){
		cin>>u>>x;
		v[u].push_back(x);
		v[x].push_back(u);
	}
	memset(dp,-1,sizeof(dp));
	v[0].push_back(1);
	dfs(0,0,0);
	cout<<max(dp[0][0],dp[0][1]);
	return 0;
}

'algorithm' 카테고리의 다른 글

A->B  (0) 2022.03.24
1377 버블소트  (0) 2022.03.22
KMP  (0) 2022.03.03
공항,암호코드  (0) 2022.02.16
곱셈, 이분탐색  (0) 2022.02.02