T(N) = N개의 색깔을 사용했을 때 답이 나오는 트리의 최소 크기

라고 정의합니다.

1. 자명히 T(1) = 1입니다.

2. T(i) >= T(i-1) + T(i-2) ... T(1) + 1입니다. 최소의 트리 T(i) 를 생각해봅시다. 해당 트리에는 i번 색의 노드가 하나 존재할 것입니다. 이 트리에 인접한 노드들은 i-1, i-2, i-3 .... 1의 색깔을 가집니다. 서브트리들의 크기는 최소 T(i-1) 이상입니다.

이를 통해 T(N) >= 2^(N-1) 임을 증명할 수 있습니다. 

koosaga 님 조금만 더 자세히 설명해주실 수 있나요?

T(i-1) 도 N개의 서브트리를 가질수있고 T(1)도 그런거같은데

어째서 이게 2^(N-1)이 되는지 궁금합니다.

지식없이 여쭤봐서 죄송합니다.

N개의 서브트리를 가진다는 게 무슨 말씀인지 모르겠습니다. 질문을 조금 더 정확히 해 주실 수 있나요?

음 제가 처음부터 이해를 잘못했는지 정확히 여쭙질 못하겠네요..ㅠ

2. T(i) >= T(i-1) + T(i-2) ... T(1) + 1입니다. 최소의 트리 T(i) 를 생각해봅시다. 해당 트리에는 i번 색의 노드가 하나 존재할 것입니다. 이 트리에 인접한 노드들은 i-1, i-2, i-3 .... 1의 색깔을 가집니다. 서브트리들의 크기는 최소 T(i-1) 이상입니다.

이를 통해 T(N) >= 2^(N-1) 임을 증명할 수 있습니다.

라고 하셨는데 2번에서 결론이 2^(N-1)이 도출되는게 이해가 안되서요..

정말 옛날 글이긴 하지만..

T(i) >= T(i-1) + T(i-2) + ... + T(1) + T(0) >= 2* (T(i-2) + T(i-3) + ... + T(1) + T(0)) >= 4*(T(i-3) + ... + T(0)) >= ... >= 2^(i-1)*T(0)