크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
※경희대학교 정치외교학과 25학번 단톡방 개설 공지※ 안녕하세요! 경희대학교...
-
강기분 하… 1
아직도 상품준비중이네여….ㅜㅜㅜㅜㅜㅜㅜ
-
하 원서 진짜 스트레스….
-
초대형과인데 이럼 발뻗잠각을
-
아무리 생각해도 난 운이 없음 걍 남들은 다 하나씩은 한다는 찍맞을 난 평가원...
-
시발 4
시발
-
머구러셀에서 그 2개 한다는데
-
오호……갑자기 합격권에 사람이 차기 시작함….
-
어디감?
-
어차피 크리스마스 아니어도 맨날 할테니까...
-
사탐 교재패스 0
사탐 교재패스는 너무 사치인가요?? 쌤들마다 유명한 분야가 나눠져잇잖아요 예를들면...
-
낙지에서는 고대 공대 교과우수가 6칸인데 텔그는 50%에요 교과우수라 표본이 좀...
-
“40년전 무임승차 이제야 갚아요” 부산역에 200만원 놓고 사라진 여성 2
40년 전 기차에 무임승차한 여성이 부산역에 200만 원을 놓고 사라졌다. 24일...
-
커트라인에서 +- 1점 내외로 움직이고 인기많은 소수과임..
-
이건 많이 간지인데? 재단은? 서울특별시 이사장은? 서울특별시장
-
가군에 고대 기공, 신소재 4칸 성대 반시공 6칸 지능솦 7칸 어디 쓰는게 나을까요??
-
사랑했지만 1
그대를 사랑했지만
-
이런과 로스쿨 생각 없는데 가면 많이 힘든가요?
-
잘 몰라서 그런데 이 두 학부에 큰 차이가 있나요?? 검색해도 잘 모르겠어서요...
-
키키킼ㅋ
-
ㅎ
-
크아아아어ㅏㄱ개시발랸들아씨발내가뭘잣못ㅎ햇ㅅ늨ㄴ데씨밯짘짜 아니시ㅇ발왜대체...
-
성대 사과 인과 0
군 옮긴거 영향 얼마나 받을까요? 인과가 사과보다 입결 높아질 수도 있을까요?
-
생기부도 그냥 그저그런수준이면 어디라인 넣나요
-
구글에 박제되나
-
문과 표본이 너무 안 찬 것 같은데 추합 끝나면 우수수 들어올까요?
-
인과계랑 싸웠나 너땜에 가군을 못지르잖아
-
안녕하세요 12
술좀마셨어요 행복버튼ON
-
지금 밖에 사람 많을거라고 내일 하자 하시네 오늘은 걍 돈까스 시킴
-
전화 추합 3
한양대 융전 예비 앞번호 떠서 낼이나 모레 전화 추합 될 것같은데.. 이미 고대...
-
크리스마스인데 연말 분위기나 내자
-
ㅈㄱㄴ
-
ㅇㅈ 3
이건 제 풀떼기 하루종일 집에만 있기 내일도 그럴 예정임••
-
정시로만 대학가려는사람중 영어 1비율이 작년보다 그렇게 많진않다 가 정배인가요?
-
서성한 정도 대학인데 한 70%정도 들어왔을까요?
-
폰배경ㅇㅈ 4
.
-
공대 어느정도 갈 성적이에여?? 경희대 시립대 정도인가요?
-
“40년전 무임승차 이제야 갚아요” 부산역에 200만원 놓고 사라진 여성 0
40년 전 기차에 무임승차한 여성이 부산역에 200만 원을 놓고 사라졌다. 24일...
-
자연계열 어디까지 가능? 기공, 물리 생각중
-
전남의대 05학번 가정의학과분은 언제 가실련지..
-
맛없어요!! 마트에서 가성비샴페인사서 그런가
-
ㅇㅇ
-
-
왜조용함? 4
다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어...
-
"정시"로 대학 못갔으니까 "늦게" 가면 되는데 ㅋㅋㅋㅋㅋㅋ
-
ㅇㅇ... 클쓰 후로 최종컷에 수렴함?...?
-
는 어그로구요 학고반수해서 다른 곳으로 옮길 예정인데 학고반수 하기 전 오티만...
-
내가 걔보다 못한게 뭔데... 시발진짜뭔데내가 어? 어? 어? 응?
-
7시되니까 딱 지옥철 풀리노 강남역지나와서 그런가
-
98 92 2 79 99가성대경영5칸인데 92 90 2 92...
고능아ㄷㄷ