크리스마스 트리 꾸미기
게시글 주소: https://9.orbi.kr/00070797422
사실 이건 아니고 백준 문제임
[BOJ 16468] https://www.acmicpc.net/problem/16468
요약) 노드가 N개고 높이가 K인 서로 다른 이진 트리의 개수를 100,030,001로 나눈 나머지를 구하시오.
(단, N과 K은 모두 300 이하의 자연수이다.)
=============================================
딱 봐도 다이나믹 프로그래밍으로 풀어야 될 것 같은 문제
D[n][k] : 노드가 n개고 높이가 k 이하인 서로 다른 이진 트리의 개수 (n, k는 0 이상의 정수)
로 정의하면 출력값은 D[N][K] - D[N][K - 1]의 값을 100,030,001로 나눈 나머지가 되어야 함
굳이 이렇게 정의하는 이유는 D[N][K]가 바로 정답이 되도록 정의하면 점화식을 세우는 게 상당히 골치 아파짐
일단 D[n][k]의 정의에 따라 다음과 같이 점화식을 구할 수 있음
특수한 케이스도 살펴보면
높이가 k인 이진 트리의 노드는 최대 2^k - 1개이므로 n ≥ 2^k일 경우 D[n][k] = 0임
또한 B[n]: 노드가 n개인 서로 다른 이진 트리의 개수 (n은 0 이상의 정수) 로 정의하면 n ≤ k일 때 D[n][k] = B[n]임
여기서 B[n]은 다음과 같이 점화식을 구할 수 있음
이제 나머지의 성질을 잘 이용해서 아래처럼 코드를 짜면 끝
시간복잡도는 O(N²K) = O(N³) 이므로 충분히 시간 제한 내에 들어옴
0 XDK (+1,000)
-
1,000
-
자야지 6
잠뇨
-
산타 9
미소녀 산타는 왜 없는거시에요
-
자러감 7
내일 하루 참아본다
-
유타랑 리카때나올때 진짜 울뻔함
-
한국정발하면저걸로바꿔야지
-
근데 막 파마 했는데 16
보글보글 머리 되면 어캄요
-
오르비할거면 오르비만 해라.
-
ㅂㅂ
-
안돼 가지마!!!
-
저능부엉이
-
항상 댓글 달러 갓는데 10
나보다 빠른 댓글이 하나 달렷다?한 명밖에 없음
-
어제 하루종일 내가 봤는데 둘 다 거의 안왔음
-
그 상태에서 살도 찜
-
ㅋㅋ 동지들
-
초딩때 한입했다가 죽을뻔해서 직접 사서 먹어본적이없는... 요즘엔 계란 올려가지고...
-
저는 친구없는데 어떻게 만드셨나요...
-
애니프사 키메타,ㅇㅈ메타 열지 않기 키,얼굴,연애로 ㄱㅁ하지 않기 ->이거만 지켜도 호감된다 ㄹㅇ
-
막상 좋아하는 사람 보면 이상형과는 좀 거리가 있는 듯요
-
전 잡니다 9
ByE
-
진짜 위기는 7
이 시간에 잠이 오지 않는 여러분들의 생체 리듬입니다
고능아ㄷㄷ