크리스마스 트리 꾸미기
게시글 주소: https://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
-
간단한 테스트 10
오른쪽입니다
-
닉변 왜 했지 8
아낄걸 하아...
-
노잼인데 4
뭐가재밌을까
-
-
쓸쓸하게. 쓸쓸히. 야심한 밤에
-
대물 3
ㅈ
-
그것이숙명
-
Tim 시작 0
Tim 하면 다음주에 시작하구… 내신땜에 진득하게 못 할 거 같아서 또 5월 초부터...
-
5분 넘었는데도 안풀리면 답지봐도 됨? 님들은 어케하심?
-
개학하고 공부 안잡히긴했는데 3평망하고 더안잡히는듯.. 공부패턴같은걸...
-
카오리의 편지는 언제나 슬퍼 그냥 교과서다
-
독서 수특? 0
독서 수특 하는게 좋나요? 굳이인가요
-
대학가서 보여줘야했는데 !!!!!!
-
【단독】 2026 수능, 영어 절대평가 폐지 확정… 역대급 입시 대혼란 예고 17
교육부 관계자에 따르면, 2026학년도 대학수학능력시험(수능)부터 영어 절대평가가...
-
-
백업해둘걸 클났다
-
사랑을 논할 자격이 업다...
-
기억하는 사람 있으려나
-
그렇습니다
-
너무 어렵네. 할 말은 많고. 막 울거같고
-
-
만우절 기념 3년간 좋아했던 고등학교 친구한테 고백하겠어 12
남고출신입니다
-
단, 1일 한정
-
-
벌써 1년의 1/4이 다 간 거임
-
.
-
그 날 날씨가 좋았어요 바람도 시원하고
-
올해 국어는 0
EBS 6 9모 학습이 끝이지 않을까요... 수학 탐구 하기도 모자람
-
새벽 경제 야르 0
영호 아저씨 볼뽀뽀 마렵네 으흐흐
-
약간 생겨먹은게 섹스 같음 안그래도 sex라는점에서섹스인데 c...c까지있어...
-
어쩌지 고백할까
-
24때 5가 1개라 충격이었는데
-
-
자라 7
잠
-
하 못참겠다 이 정벽 가시나 대구로 쏩니데이
-
하반기에 국어 제외하고 실모 위주로만 공부할 거고 본인 생각하고 있는 건 국어 /...
-
윤석열 원영턴 2
-
NM? 너 재능있어 열심히 해
-
나의 말:ㅎㅇㅎㅇ ㅋㅋ 오르비에 어그로 글 쓰려고 하는데, 명문대 나와도 인생 망한...
-
이렇게 기분이 축 쳐질때 해결책이 있을까요..?
-
그래보임
-
어렵다...ㅋㅋ 운좋게 적백달성 특이사항은 미적 28,30이 엄청 쉽게 나왔다...
-
허수물화러 아시는분 계실려나
-
발상이 한 20년쯤 앞서 있음
-
이거 실친들은 다 아는 닉네임인데
-
돌아보니 몇 안되는 정시공부할 수 있는 시간이였는데..
-
반수할 예정인데 송파메가스터디 재종 가는게 나을까요 아님 잇올 다니면서 수학 단과...
-
스블 질문 0
스블 회독하는거로 기출 충분함?
-
-
ㅇㅇ 30분뒤부터
고능아ㄷㄷ