크리스마스 트리 꾸미기
게시글 주소: https://ui.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 (+2,500)
-
1,000
-
1,000
-
500
-
현역이 그냥 없던데...
-
너무 쫄린다 2
설마 f를 받진 않겠지…
-
-
-
친구 없다면서 ㅇㅈ은 실친이 볼까봐 못하겠다고하네요~
-
정시 산출식 알려주세요...
-
기차지나간당 4
부지런행
-
개인적인 좌우명 4
네가 해결할 수 없는 일에 스트레스 받지 마라 그냥 아무 글이나 난사 중
-
다들 인증하고 아무렇지 않게 넘기던데 잘안되나보오
-
국수 먹고 싶다 4
아악 배고파아ㅛ ㅜㅜ
-
잊은 줄 알았는데 꿈에 나와요 일하러 가야하는데 하
-
시발
-
-
그래도 나는 거침없이 하이킥…
-
근데 이건 정말 나만 알고 싶은건데..
-
심장 아프다 4
요즘 너무 무리했나 따흐흑
-
ㅇㅈ 4 6
눈내린서울시립대인증이라네요 진지하게 수목한정 국내대학 원탑 홍보 안해서 그렇지...
-
제가 현역6 재수5인데 국어만 성적이 안오르거든요.ㅠ 올수능 최소2는...
-
비교내신 1
적용대상이면 불리한건가요??? 수능성적으로 반영한다는데
-
고능아ㄷㄷ