크리스마스 트리 꾸미기
게시글 주소: https://io.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
-
ㅇ
-
나도 무물... 6
ㄱㄱ
-
나 화날라그래
-
ㅇㅈ ㅇㅈ ㅇㅈ 8
ㅇㅇ
-
원래 잘했던 사람들 말고 등급 낮았다가 높아진 분들중 답주시면 좋을거같아요 저처럼...
-
디시인사이드라 했음
-
재수로 수학 올리신분 13
반수하려고 지금부터 공부 시작하려는데 작수 공통1틀(22) 미적4틀(27 28 29...
-
안뇽>< 11
-
K-Flip이 데저트이글 샘플링이래서 실리카겔 노래 쭉 듣고 있는데 내 취향이랑 좀...
-
-
지금 현재 정승제t 개때잡 개기팔시 솔루션 진행하고 있어요 (6월까지 일정이 있음)...
-
젠장못잤어 2
크아악 버스에서자야겠다
-
난 학벌이라도 높여야겠다
-
반갑구만
-
걍 평범한 한남임뇨
-
정시로 경희대나 외대 진학하게 될 것 같습니다. 오르비에 워낙 문과는 서성한 밑으로...
-
둘 중 더 좋은거 투표 12
.
-
오늘 찍은 사진 ㅇㅈ 11
메타 정상화를 위해.
-
다들 굿밤 3
행복하시길
-
안녕히 주무세요 4
양치햇습니다 5시 알람 맞춰두고 자러갑니다 ㅂㅂ
고능아ㄷㄷ