2533번: 사회망 서비스(SNS) www.acmicpc.net 이 문제는 트리로 나타낼 수 있는 친구 관계에서 모든 개인이 새로운 아이디어를 수용하기 위한 최소 얼리 어답터의 수를 구하는 문제로, 얼리 어답터가 아닌 사람이 새로운 아이디어를 수용하기 위해서는 그 사람과 인접한 사람들이 모두 얼리 어답터여야 한다. 이 문제는 이전의 트리의 독립집합 문제와 유사한 방법으로 해결할 수 있다. 다만, 각 노드마다 자신이 얼리 어답터가 되는 경우와 그렇지 않은 경우로 나눠서 dynamic programming을 적용한다. 각 노드 u마다 자신이 얼리 어답터가 되는 경우 u를 루트로 하는 서브트리에서 u의 각 자식 노드가 얼리 어답터가 되든 안 되든 상관없으므로 두 경우 중 최소가 되는 얼리 어답터의 수를 u의 ..
