반응형 트리1 백준 2533번 : 사회망 서비스(SNS) (C/C++) 백준 2533번 최소 얼리 어댑터의 수를 구하는 문제이다. 전형적인 트리dp문제라고 볼 수 있다. 이문제를 풀기 위해서는 트리는 트리로 구성되어있다는 개념을 이용해야한다. 우선 k=1을 얼리 어댑터, k=0인 경우를 얼리 어댑터가 아닌 경우라고 할때, dp 배열을 아래와 같이 정의한다. dp[n][k] : n이 k이고, n을 루트로하는 서브트리의 최소 얼리 어댑터의 수 1. k=1일때, 자식 노드들이 1이여도 되고, 0이여도된다. n의 모든 자식 노드를 nx라고 할때, 다음이 성립한다. 2. k=0일때, 모든 자식 노드들이 1이여야만 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.. 2023. 5. 9. 이전 1 다음 반응형
