백준 2533 SNS

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
N = int(input())
Tree = [[] for _ in range(N+1)]
check = [True for _ in range(N+1)]
for _ in range(N-1):
    u, v=map(int, input().split())
    Tree[u].append(v)
    Tree[v].append(u)
dp = [[0,0] for _ in range(N+1)]
def dfs(cur):
    check[cur] = False
    dp[cur][0] = 0 #포함 x
    dp[cur][1] = 1 #포함 o
    for i in Tree[cur]:
        if check[i]:
            dfs(i)
            dp[cur][0] += dp[i][1]
            dp[cur][1] += min(dp[i][1], dp[i][0])
dfs(1)

print(min(dp[1][0], dp[1][1]))

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

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

 

다소 생소하면서도 dp에 대한 생각을 확장시켜준 문제

 

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