LC968: Binary Tree Cameras

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

  • 한번 푼 문제는 다시 풀기는 하지만, 개선된 풀이를 다시 떠올리기는 어렵다.
  • 아 이거다 하고 다시 풀었는데, 역시나 예전이랑 똑같이 풀었다 -_-.
  • Tree-DP의 핵심 아이디어는 역시나 중복된 계산 메모하기. 한 Node에 대해 두번 탐색하는 함수를 부른다면, 반드시 저장해야 한다.
  • 개선된 풀이의 핵심 아이디어는 Mark-and-Sweep.
    • Leaf Node의 부모에 Camera를 두고 cover된 node만 제거해 나간다면, 최적화를 찾을 수 있다는 가정이다.
    • Greedy 문제의 어려움점은 맞는것 같으면서도 증명이 안된다는것… 이것도 그렇다.