크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
성비 한 9:1까진 아닌 듯한
-
나랑 애니볼래? 8
-
30번에삼각함수가나오기때문
-
-
에리카 공대, 인하대 상경, 광운대 상경 다 안정떠서 고민이네요 안정카드를 이...
-
자야지 4
-
자야겠다 8
슬슬 졸리네
-
ㅇㅈ 9
-
배고파 배고파 배고파 배고파 배고파
-
몇몇은 동태가 수상한데 11
놀러가놓고 슬쩍슬쩍 오르비에 쓰나봐.
-
잘자요 4
다들메리크리스마스
-
입으면 덥고 벗으면 추움 반만 입을까
-
-
ㅅㅎ고 다닌다고 작년에 친구한테 들었던 것 같은데
-
2021년 후반기정돈 되어야 좀 실감나는듯
-
잘가... 이번엔 진짜 간 것 같은데 대학생활 잘하고
-
-
1. 테-무에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
인싸 나가 8
-
25수능 물1 현장풀이입니다. 18번은 현장에서 미지수 범벅으로 풀어서 공부에 딱히...
고능아ㄷㄷ