[백준] 12928. 트리와 경로의 길이

https://www.acmicpc.net/problem/12928

문제 요약

• 노드가 n개이고 단순경로가 s개인 트리가 가능한지 판단
• 단순경로 : 3개의 노드가 이어진 형태들의 집합(중복 없이)

접근법

• 1개, 2개일때는 만들 수 없음
• 발상
  • 노드가 2개 이상인 기존 트리에 노드를 하나 붙이면 단순경로가 늘어날 것임 : 새로운 노드와 연결되는 형태가 발생
  • 기존 트리에서 노드를 하나 이어붙일때 단순경로가 어떻게 변하는지를 관찰
  • 새로운 노드를 $X$ 기존 트리에서 연결할 노드를 $A$라고 하면
  • $X$를 $A$에 붙이면 $A$의 인접 간선만큼 단순경로가 증가할 것임($= count$)
  • 그리고 $A$의 인접간선은 $count+1$, $X$의 인접간선은 $1$이 될 것임
  • 이 상태에서 새로운 노드 $Y$를 $A$에 연결하면 단순경로는 $count+1$만큼 증가하고 $A$의 인접간선은 $count+2$가 됨
• 정리
  • 2개의 노드로 된 트리부터 시작함. 새로 붙일 수 있는 노드는 $N-2$개가 있음
  • 임의의 노드 $A$에 새로운 노드를 계속 붙여나감
  • 단순경로는 1, 2, 3, ... 만큼 증가할 것이고, 증가량은 1, 1+2, 1+2+3, ...이 될 것임
  • 사용할 수 있는 노드는 $N-3, N-4, ...$로 감소할 것임
  • 임의의 숫자 S가 {1+2+....} + {1+2+3+....} + ... {1+2+..}의 형태가 될 수 있는지를 확인해봄
  • dp[사용할 수 있는 노드][추가할 수 있는 단순경로] = 가능/불가능 으로 정의하면
  • 현재 상태에서 단순 경로를 1, 1+2, 1+2+3, ... 만큼 증가시켜보고, 이후에 사용할 수 있는 노드에서 같은 작업을 반복해봄(이후에 사용할 수 있는지는 dp값을 이용)
  • S = 1000이기 때문에 각 dp당 최대 $x * (x + 1) / 2 = 1000$을 만족시키는 값 x만큼 반복할것임(44~45정도)
  • $O(N*S*\sqrt{S})$