Today's Challenge

https://leetcode.com/problems/binary-tree-cameras/

Binary Tree Cameras - LeetCode

Hard 난이도의 문제.
여러 가지로 풀 수 있는데, DP가 제일 쉬워 보여서 선택!

하나.. 소스가 간단해 보였을 뿐.. 이해하기는 꽤 어렵

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        def solve(node):
            if not node:
                return 0, 0, float('inf')
            L = solve(node.left)
            R = solve(node.right)
            
            dp0 = L[1] + R[1]
            dp1 = min(L[2] + min(R[1:]), R[2] + min(L[1:]))
            dp2 = 1 + min(L) + min(R)
            
            return dp0, dp1, dp2
        
        return min(solve(root)[1:])