[usaco] 2.3 Cow Pedigrees - usaco
2009.08.15 13:13 Edit
Pedigrees는 혈통이라는 뜻이란다.
소가 몇마린지 그리고 깊이가 얼마인지 주어지면 만들수 있는 binary tree는 몇개인지 출력하는 문제이다.
깊이가 k일때 node는 최소 2k-1개 최대 n개이고
왼쪽 node가 i개이면 오른쪽 node는 n-1-i가 되고
왼쪽 깊이가 k-1일때 오른쪽 깊이 1~k-2까지 구한다음 *2해주고(왼쪽 오른쪽 바꾼거)
양쪽이 둘다 k-1일때는 그냥 더해주면 된다.
풀고나서 정리하면 깔끔하고 쉬운데
왜 풀때는 막막해서 그런지 한없이 복잡해 보인다.
이런 문제 좀 더 풀다보면 나아지겠지?
소가 몇마린지 그리고 깊이가 얼마인지 주어지면 만들수 있는 binary tree는 몇개인지 출력하는 문제이다.
깊이가 k일때 node는 최소 2k-1개 최대 n개이고
왼쪽 node가 i개이면 오른쪽 node는 n-1-i가 되고
왼쪽 깊이가 k-1일때 오른쪽 깊이 1~k-2까지 구한다음 *2해주고(왼쪽 오른쪽 바꾼거)
양쪽이 둘다 k-1일때는 그냥 더해주면 된다.
풀고나서 정리하면 깔끔하고 쉬운데
왜 풀때는 막막해서 그런지 한없이 복잡해 보인다.
이런 문제 좀 더 풀다보면 나아지겠지?
Trackbacks 0
Comments 2
-
Toivoa
2009.08.15 14:23
*.75.101.10
