[2533번] 사회망 서비스(SNS)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

두가지 방법으로 문제를 바라 볼 수 있다.

1. 

현재 노드가 얼리어답터면 -> 인접한 다음 노드는 얼리어답터가 아니다.

현재 노드가 얼리어답터가 아니라면 -> 인접한 다음 노드는 얼리어답터이거나 얼리어답터가 아니다.

2.

현재 노드가 얼리어답터면 -> 인접한 다음 노드는 얼리어답터이거나 얼리어답터가 아니다.

현재 노드가 얼리어답터가 아니라면 -> 인접한 다음 노드는 얼리어답터이다.

이 방식을 이용하여 dp를 적용한다.

이때 dp[i][j]의 의미는 i번째 노드가 j == 0일때는 얼리어답터가 아닐 때의 dp, j == 1일때는 얼리어답터일때의 최대 혹은 최소인 dp값을 가지게 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <memory.h>   using namespace std;   vector<int> vc[1000002]; int dp[1000002][2];   int dy(int prev, int here, bool chk) {     int &ret = dp[here][chk];       if (ret != -1)         return ret;       ret = 0;          for (int i = 0; i < vc[here].size(); i++)     {         int next = vc[here][i];           if (next == prev)             continue;           if (chk)             ret += dy(here, next, 0);         else if (!chk)             ret += max(dy(here, next, 1) + 1, dy(here, next, 0));     }       return ret; }   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n - 1; i++)     {         int from, to;         scanf("%d %d", &from, &to);           vc[from].push_back(to);         vc[to].push_back(from);     }       memset(dp, -1, sizeof(dp));       printf("%d", n - max(dy(-1, 1, 0), dy(-1, 1, 1) + 1));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory.h>
 
using namespace std;
 
vector<int> vc[1000002];
int dp[1000002][2];
 
int dy(int prev, int here, bool chk)
{
    int &ret = dp[here][chk];
 
    if (ret != -1)
        return ret;
 
    ret = 0;
    
    for (int i = 0; i < vc[here].size(); i++)
    {
        int next = vc[here][i];
 
        if (next == prev)
            continue;
 
        if (chk)
            ret += min(dy(here, next, 0), dy(here, next, 1) + 1);
        else if (!chk)
            ret += dy(here, next, 1) + 1;
    }
 
    return ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n - 1; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        vc[from].push_back(to);
        vc[to].push_back(from);
    }
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", min(dy(-1, 1, 0), dy(-1, 1, 1) + 1));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>