tree-dp 썸네일형 리스트형 BOJ 18770 - 불안정한 물질 (P2) #dfs #tree-dp 구현이 짜증나는 문제다. 문제는 꽤 재밌는데, n개의 노드와 n개의 간선이 있다. 이상태에서 인접하지 않은 정점만 골라서 최대 점수를 얻는 문제다. 만약 n개의 노드가 다 연결되어 있다면 그 그래프는 트리에 하나의 간선을 추가한 형태일 것이고, 그 간선에 의해 indegree가 2인 정점이 생긴다. 그래서 이 정점과 그 부모를 골라내서 이 정점들끼리는 미리 고를지 말지를 결정해두고, 간선을 하나 지우면 트리가 된다. 그 이후로 트리 dp를 돌리면 된다. 과연 이게 가능할까? 생각해보면 트리에서 간선만 하나 추가한 형태이기 때문에, 고려할 정점은 무조건 3개이다. 그래서 이 3개끼리 잘 케이스를 나눠가면서 연결그래프를 유지하되 간선을 하나 지울 수 있다. 그러면 트리가 되므로 .. 더보기 이전 1 다음
