백준(BOJ) 2213 트리의 독립집합 **

# 다이나믹 프로그래밍

너무 만만하게 생각했는데 생각보다 까다로운 디피 문제였다...

이 문제가 다른 디피들과 다른 이유에 대해서 간단하게 보자.

기본적인 하나의 디피라고 생각한다면

5개중 2개이상 연속으로 선택할 수 없을때 최대 값을 구하는 문제이다.

이 문제는 이런 기본 디피가 여러개가 연결되었을때 어떻게 해결하냐를 물어보는것 같다.

# arr : 노드의 가중치

# dp[i].first : 선택 하는 경우

# dp[i].second : 선택 안하는 경우

잘 생각해 보면 다음과 같이 연결된 부분의 디피를 해결할 수 있다.

dp[선택 하는 경우] = dp1[선택 안한 경우]+dp2[선택 안한 경우] ...

dp[선택 하는경우] = max(dp1[선택 한 경우],dp1[선택 안한 경우]) + max(dp2[선택 한 경우],dp2[선택 안한 경우]) ...

그냥 이전의 경우들을 더해주면 된다...

이런 다음 역으로 선택한 노드들을 찾아 주면된다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 10005
#define INF 987654321
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n,a,b,arr[MAX];
pi dp[MAX];
bool visit[MAX];
vector<int> node[MAX],v;

pi dfs(int cur)
{
    dp[cur]={arr[cur],0};
    visit[cur]=true;
    for(int i=0;i<node[cur].size();i++)
    {
        int next=node[cur][i];
        if(!visit[next])
        {
            pi tmp =dfs(next);
            dp[cur].first+=tmp.second;
            dp[cur].second+=max(tmp.first,tmp.second);
        }
    }
    return dp[cur];
}
// 각 노드에 대한 dp 값!

void find(int cur,bool tf)
{
    bool sel=false;
    visit[cur]=true;
    if(!tf&&dp[cur].first>dp[cur].second)
    //(실수한 부분)이전 노드가 선택되지 않고 && 선택의 경우가 비선택보다 큰경우 경로 추가
    {
        sel=true;
        v.push_back(cur);
    }
    for(int i=0;i<node[cur].size();i++)
    {
        int next=node[cur][i];
        if(!visit[next])
            find(next,sel);
    }
}
// 선택한 경로 찾는 과정

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        node[a].push_back(b);
        node[b].push_back(a);
    }
    pi ans=dfs(1);
    printf("%d\n",max(dp[1].first,dp[1].second));
    // 우선 dp를 만들어 준다.
    
    fill_n(&visit[0],MAX,false);
    find(1,false);
    sort(v.begin(),v.end());
    for(auto iter:v)
        printf("%d ",iter);
    // 경로 출력 과정
    
    return 0;
}