알고리즘/Boj
BOJ 2523 사회망 서비스(SNS) 풀이
533 [링크] [풀이] ps를 한창하던 2018년, 여름 즈음에 이 문제를 봤던 기억이 있다. 다른 알고리즘에 비해서 dp는 너무 어렵게 느껴져서, 풀다가 포기했던 기억이 난다. 아마 같이 문제를 봤던 형님은 얼마 안 가 풀었는데, 답지를 보자니 dp는 답지보면 너무 쉽게 느껴져서 다음에 풀어보기로 하고 군 입대를 했다.... 잡설은 뒤로하고, tree에서 dp를 쓰는 특이한 문제로 기억된다. 자, dp table $dp[i][j]$를 $j$가 0일 경우 => $i$번째 node가 얼리어답터가 아닐 때 $i$의 subtree를 완성시키는데(모두 수용하도록 하는데에) 필요한 최소 얼리어답터 수 $j$가 1일 경우 => $i$번째 node가 얼리어답터일 때 $i$의 subtree를 완성시키는데필요한 최소 ..
