크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
자러감 7
내일 하루 참아본다
-
유타랑 리카때나올때 진짜 울뻔함
-
다시 태어난다면 3
ㅓㅏㅣ로 태어나고 싶다
-
오르비호감고닉금테그분...
-
료이키 텐카이 0
후쿠마미즈시
-
뻘글 폭격 1
전개
-
몬난놈들끼리는 6
닉만봐도 즐겁다
-
그때도 과탐 과외 수요 있나요?
-
성인이 되면 0
뭐하지
-
사설에선 3도 진짜 많이 받아봤고 결국 수능도 2고
-
진학사표본 보는데 수학 탐구 6,7 이런데 국어 2 사탐2 면 붙네…. 흠… 이건 좀…?
-
+백분위대학인 경기대인데 왜 작년 커트보다 올해 최종컷이 낮은지도 알려주세요
-
30번에삼각함수가나오기때문
-
야스의벽 즐기는야스 이 두명이 특히 ㄹㅇ
-
반수 마렵네ㅋㅋㅋㅋ
-
질받 5
식물 좋아하는 대학생임뇨
-
크리스마스 기념
-
한 약 수 다 붙었습니다 이것저것 굉장히 많이 고민해봤습니다 현재 업계 평균...
-
Was turn?
-
ㅇㅈ 11
쩝 심심한데 다들 ㅇㅈ해주세요 흐려서 잘 안보이지만 ㅇㅈ…….
-
고2 모고가 생각보다 실력을 잘 알려줄 수도 있음 19
2023년 고2 11월 모의고사 (물1지1) 2025학년도 9월 평가원 모의고사...
-
오늘의 상식 0
소수는 primitive root를 가진다.
-
재수하게된 고3입니다ㅜㅜ 급하게 생기부 채워야 하는데 설문조사가 필요합니다...
-
생색좀 낼게오 13
어렸을때 롤링페이퍼 텅텅 비어있던게 별로 좋은 기억이 아니었어서 최대한 한명도...
-
고딩시절 ㅇㅈ 10
왜케 양아치처럼 나왔지 생긴건 저랬는데 조용했음•• 술담배도 안함
-
정권 바뀐다면 수능이 어떻게 바뀔지도 모르겠고 재수 때 윤석열 출제 지시 파문...
-
ㅇㅈ 2
-
ㅅㅎ고 다닌다고 작년에 친구한테 들었던 것 같은데
-
ㅇㅈ 5
잘 찍었죠
-
오르비에 ai잇남 13
그 스스로 학습하는 ai (머라하더라)
-
내신 문과 3.21정도 나왔었는데 연의는 꿈도 못 꿀만큼 불가능할까요? 내년이 처음...
-
이브날 데이트 ㅇㅈ 16
oz상과 노베 데이트캄오실데석페...
-
소신발언 ㅇㅈ 2
(물리)
-
1. 테-무에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
올해도 솔크 ㅅㅂ
-
무물보 25
-
군대가기싫어요
-
나도 아직 300개는 멀었는데
-
여르비 ㅇㅈ 11
낚시 성공
-
-
반응이 없엇어서 울엇어
-
감사합니다 진짜로 8ㅁ8
-
진짜 위기는 7
이 시간에 잠이 오지 않는 여러분들의 생체 리듬입니다
-
사실 뻥임.
-
뿌우우웅 11
-
성비 한 9:1까진 아닌 듯한
-
시무룩한 강아지에 나 아포 이러니까 너무 슬프잖아요 아프지마 래브라도 리트리버야 ㅠ(추정)
-
다들 주무십쇼 0
어우 너무 졸리다
-
평단가가 굉장히 낮은 종목은 함부로 안 사야겠다… 좀만 올라가거나 내려가면 변동이...
-
저도 슬슬 자러갈게요 다들 수고 많으셨어요!
고능아ㄷㄷ