dkwkekzz   2달 전

안녕하세요. 질문을 드리게 되었습니다.

70749a410686944641745434808c1d4d.png

위는 이 코더스하이3번문제에 대한 풀이 중 일부분인데요. 이 부분이 이해가 되질 않습니다. 

첫번째그림에서는 첫번째 인접노드에 대해서만 생각하는 것일까요?  그럼 T(u, 4) - 루트u를 포함하는 그룹의 크기가 4일 때의 (경우의 수, 최소 컷수) = T(v1, 3)처럼 될 것입니다.

2개 라면 u를 포함하여 그룹의 크기 4를 만들 때의 값이므로 다음 식을 적용할 수 있겠네요.

4eb221f61408653d34019629b0f752b9.png

첫번째식과 이 식을 어떻게 연동해야 할지조차 꽉막힌 변기처럼 떠오르지가 않습니다 ㅜㅜ 

게다가 3번째 그림에서는 1,2번째노드에서 합친것과 3번째노드를 합치네요. 예를 들어 T(u, 4)일 때를 생각한다면 1,2의 합에서 고르는 k개와 3번째 노드에서 고르는 i-1-k개가 있겠습니다.  1,2번째 노드를 합친 것을 어떻게 표현하나요? 어떻게 일반화시켜야 첫번째와 3번째의 경우를 적용시킬 수 있나요?

결국 자식이 2개일때만 적용할 수 있는 식이군요. 1개이거나 2개가 초과하면 어떻게 이해해야 할까요? ㅜㅜ

말은 되는데 구현이 안 됩니다ㅜㅜ 

연관 지식이나 좀더 풀이해주시면 정말로 감사드리겠습니다~~~ 즐거운 명절되십시오~ 

댓글을 작성하려면 로그인해야 합니다.