이 문제는 N이 크지 않아서 dfs 로 풀어도 가능하다.다음과 같이 각 노드에 대해 뻗어 나가는 경우는 2개이다.1. 인사를 한다2. 인사를 안한다트리로 나타내면 다음과 같고, 시간복잡도는 2의 N승이다.하지만, 제한조건 N의 수가 커진다면, 시간복잡도를 만족하지 않을 수 있다.그럼 어떻게 최적화를 할 수 있을까? 경우의 수를 구하는 문제에서는 배낭(Knapsack) 알고리즘으로 해결할 수 있었다.같은 색 노드를 봤을 때 사실 인덱스(i)만 다르지 얻을 수 있는 행복과 현재 체력은 같다. 따라서 i 번째 사람과 인사를 안할 경우 i-1번째 사람한테서 가져오면 된다. 하지만 i번째 일때도 경우의 수가 4개 정도 존재한다. 그 중 어떤 경우의 수에서 값을 가져와야할까?이것까지 고려해주기 위해 dp는 1차원 ..
