[ BOJ 백준 1949번 - 우수 마을 ] 해설 및 코드

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

 

 

목적

우수 마을 선정 기준('우수 마을'은 서로 인접할 수 없고, '우수 마을'이 아닌 마을은 '우수 마을'과 인접해야 한다.)에 따라, N개의마을중 몇개의 마을을 우수마을로 선정하여 인원의 합이 최대가 되게 만들자.

 

접근법

1. 트리의 성질에 따라 사이클에 관한 고민을 하지않아도 된다.

2. 우수 마을이 아닌 마을이 몇개 까지 인접가능한지 따위의 것을 고려하지 않아도 된다. 그냥 인접해도 무방하다는 가정으로 설계해도 최대값을 구하는 과정에서 걸러진다. 

3. 우수마을과 인접한 마을만 우수마을에서 제외시키는 조건만 가지고, 간단히 DP로 해결하자.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
 
const int LEN=1e4+1;
vector<int> town[LEN];
int n,pop[LEN],s[LEN][2];
bool vis[LEN];
 
int sol(int i,int k){
    int& ref=s[i][k];
    if(ref!=-1)return ref;
    vis[i]=true;
    
    ref=0;
    for(int t:town[i])if(!vis[t]){
        int tmp=sol(t, 0);
        if(k==0)tmp=max(tmp,sol(t,1));
        ref+=tmp;
    }
    vis[i]=false;
    return ref+=(k==1?pop[i]:0);
}
 
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin>>n;
    f(i,1,n)cin>>pop[i];
    f(i,2,n){
        int a,b;cin>>a>>b;
        town[a].push_back(b);
        town[b].push_back(a);
    }
    memset(s,-1,sizeof(s));
    memset(vis,false,sizeof(vis));
    cout<<max(sol(1,1),sol(1,0));
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.