반응형
문제
https://www.acmicpc.net/problem/2533
2533번: 사회망 서비스(SNS)
첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에
www.acmicpc.net
풀이
트리에서 DP를 사용하는 문제입니다.
- 현재 노드가 얼리어답터가 아니라면, 다음 노드는 무조건 얼리어답터여야 함
- 현재 노드가 얼리어답터라면, 다음 노드는 얼리어답터일 수도.. 아닐 수도..
점화식은 다음과 같이 정의할 수 있습니다.
$f(n, 0) = $: n번 노드가 얼리어답터가 아님
$f(n, 1) = $: n번 노드가 얼리어답터
점화식: $f(n, 0) = f(next, 1), f(n, 1) = min(f(next, 0),f(next,1))$
소스코드
후기
기존에 우수 마을 문제와 거의 비슷한 문제여서 쉽게 풀 수 있었습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 2166 다각형의 면적 (Swift) (0) | 2023.05.24 |
|---|---|
| [BOJ] 백준 2213 트리의 독립집합 (Swift) (0) | 2023.05.24 |
| [BOJ] 백준 1949 우수 마을 (Swift) (0) | 2023.05.23 |
| [BOJ] 백준 15681 트리와 쿼리 (Swift) (0) | 2023.05.23 |
| [BOJ] 백준 17472 다리 만들기 2 (Swift) (0) | 2023.05.18 |
