문제

2533번: 사회망 서비스(SNS)

트리임에 집중하자

문제에서 사이클이 없는 트리의 형태로 입력을 제한한다고 했다. 트리라면 부분문제로 나눌 수 있다는게 엄청난 장점이다. 부분트리로 나누어서 자신의 윗 부분 문제는 해결하지 않고, 자신의 자식 부분만 얼리어답터로 만들면 된다.

Untitled

점화식을 써보자

일단 DP에 i를 루트노드로 하는 서브트리의 최소 시작 얼리어답터개수를 저장하자. 이건 바로 밑 자식들을 서브트리로 하는 부분문제의 해의 합일 것이다. 그러면 DP를 사용해야하는 이유는 무엇일까. 중복이 되는 부분은 dp[2][0]에서도 5,6,7번 노드는 호출되고 dp[2][1]에서도 호출된다.

dp[i][0] = i번노드를 루트노드로 하는 서브트리에서 얼리어답터 최솟값. i번노드는 얼리어답터가 아님.

      = sum(dp[child][1]);

dp[i][1] = i번노드를 루트노드로 하는 서브트리에서 얼리어답터 최솟값. i번노드는 얼리어답터가 맞음.

     = sum(min(dp[child][0], dp[child][1]))

code

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<int>> edge(1000001,vector<int>());
int dp[1000001][2];

int solve(int i, int j, int call){ 
	int& ret = dp[i][j];
    if(ret != -1) return ret;
    ret = j;
    for(auto child : edge[i]){
        if( child == call)continue;
        if(j == 0) ret += solve(child,1, i);
        if(j == 1) ret += min(solve(child,0,i), solve(child,1,i));
    }
    return ret;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int n,a,b;
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for (int i = 0; i < n-1; i++){
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a); 
    }
    cout<< min(solve(1,0,1),solve(1,1,1));
    return 0;
}