다이나믹프로그래밍1 BOJ 2533 사회망 서비스(SNS) 2533 사회망 서비스(SNS) [https://www.acmicpc.net/problem/2533] 문제를 읽어보시면 친구와의 관계는 Tree로 표현될 수 있다는 것을 알 수 있습니다. 이 문제는 트리 탐색과 메모리제이션을 동시에 하면서 해결 할 수 있습니다. 아래와 같은 친구관계를 가지고 있는 트리를 이용해 설명하겠습니다. 메모리제이션을 이용할 dp테이블은 다음과 같습니다 dp[i][state] : i번째 정점을 root로 가지고 있는 Subtree 에서의 최소 얼리어답터 수 : state == 0 -> 정점 i가 얼리어답터가 아닌 경우 : state == 1 -> 정점 i가 얼리어답터인 경우 우선 루트노드(1번 노드)부터 Leaf 노드까지 탐색합니다. 제일 첫번째 방문하는 Leaf 노드는 5번 노드.. 2017. 9. 24. 이전 1 다음 반응형
