문제

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

풀이

트리에 DP를 접목 시킨 문제다.

# [정점 번호][얼리어답터 여부]
dp = [[0, 1] for _ in range(N + 1)]

DP 테이블을 위와 같이 초기화 시켜 준다.
얼리어답터 여부에서 0번 인덱스는 자신이 얼리어답터가 아닌 케이스, 1번 인덱스는 자신이 얼리어답터인 케이스이다.

def dfs(start):
    visited[start] = True

    for i in graph[start]:
        if not visited[i]:
            dfs(i)
            dp[start][0] += dp[i][1]
            dp[start][1] += min(dp[i][0], dp[i][1])

트리를 전체 순회해야 하므로 dfs로 순회를 해준다. 일단 모든 노드를 순회한 뒤, 재귀를 돌아오며 DP 테이블을 갱신해준다.
dp[start][0]는 자신이 얼리어답터가 아닌 케이스이기 때문에 연결된 바로 다음 노드가 얼리어답터인 케이스(dp[i][1])의 값을 더해주어야 하고, dp[start][1]는 자신이 얼리어답터인 케이스이기 때문에 연결된 바로 다음 노드가 얼리어답터여도 되고 얼리어답터가 아니여도 된다.
그렇기에 min(dp[i][0], dp[i][1]) 중 최소값을 더해준다.

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

재귀를 돌아오며 테이블을 갱신해주었기에 순회를 시작한 노드에 최소 얼리어답터 수가 기록되어 있을 것이다.
내가 얼리어답터인 케이스, 아닌 케이스 중 최소값을 출력해주면 정답이 된다.

전체 코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(start):
    visited[start] = True

    for i in graph[start]:
        if not visited[i]:
            dfs(i)
            dp[start][0] += dp[i][1]
            dp[start][1] += min(dp[i][0], dp[i][1])


N = int(input())
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N + 1)
dp = [[0, 1] for _ in range(N + 1)]

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