크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
키 크고 ㅈㄴ 웃긴 개그맨 포지션인데 수시로 설대감 머리도 엄청 좋아서 하루에...
-
군수생인데 시간이 없어서 수리논술 준비할까 하는데 비추인가요? 목표는 부산 경북입니다
-
너무 위험이큰가...... 4는 근데 약간 5에가까운 4임
-
에혀…
-
진학사진짜하… 0
이거 발뻗잠 가능하죠? 왜 자꾸 추합권으로 잡는건가요… 163명 뽑는건데
-
낮 12시까지 자기 요즘 너무 피곤함
-
안녕하세요 저는 지금 고3 현역이고 재수를 생각하고 있는데요.. 재수를 고민하는...
-
네 이거 세개 들읍시다 외로운 이들의 캐롤
-
병신트리오 17
8칸이지만 여기를 써야 하는 새끼들..... 세얼간이 입갤 그리고 그게 나야....
-
참 좋은데…
-
오늘 3차 홈페이지에 뜬다고했는데 안뜨고 바로 전화추합 시작하더라고요 제 주위엔...
-
민주당 일각 “국무위원 5명 한꺼번에 탄핵… 국무회의 무력화땐 거부권 행사못해” 논란 0
더불어민주당이 한덕수 대통령 권한대행에게 김건희·내란 특검법 공포와 내란 상설특검...
-
난 연애보다 3
서울대에 가고싶다고!!!!!!!!! 내가 진짜 잘할게
-
인생 시이이이이발
-
아빠가 갑자기 금이 돈 다박아야한다고 하니까 그 돈은 어디서나오냐고 얘기하다가 레전드싸움;;
-
응 그래서 어쩌라고
-
가능하면 지금자고 26일아침에 일어나겠음
-
뒹굴뒹굴 1
풀떼기들과 함께하는 따뜻한 크리스마스 이브
-
아 그만 후해지라고
-
공부하자. 크리스마스날 공부하자. 다른 것 할 수 없으니까 공부하자. 누군가는 커플...
-
아무리봐도 +1마음먹은행님들이 가나군 메디컬 상향 지르고 다떨어지면 걸어놓고 반수하는데같어...
-
다들 어디감????
-
차돌짬뽕을 먹어 4
맛있을거임
-
한능검 10
공부해보신분?
-
지가기른지 어케암?ㅇㅈㄹ하고 의문사 이뒤로 손가락걸기 안하는데 여전히실수해서 울고시프다.......
-
내일 할거 1
.
-
모두 안녕하세요 6
저는 오늘 오르비에 있을겁니다.
-
개ㅈ같은 크리스마스같은건 사라져야해
-
어딜 가든 캐롤이야
-
원래 그런건지 올해가 유난히 적은건지
-
죄다 f(x)/(x-a) 꼴인데
-
진지하게 사회성 떨어지는 사람인데 아예 관심을 주지 말아야지
-
이거 아시는분?
-
3차발표도 안하고 바로 전화로 돌리는거 보니까 이제 더이상 안빠지는거같네...걍 포기해야하나
-
앙앙대겠지 나는 앙앙거리지못한다 앙앙 슬프구나 엉엉
-
저 또한 9평까지만 하더라도 4등급이였습니다..처참했죠 하지만 올바른 학습법만...
-
가나다군 폐지해 2
폐 지 해
-
ㅈㄱㄴ
-
5년제랑 4+2년제가 있던데 그럼 5년제 대학 가는 게 더 이득인 건가요 아님...
-
아.
-
많이 올린건가요 10
열심히했는데 다 떨어질 생각하면 또 서럽네요
-
4년만에 솔로크리스마스다.
-
-
오늘의 낙지 1
에휴 기대한 내가 잘못이지
-
예비 현역인데 다니던 학원 선생님께선 인강에서는 다 술술 풀리게 얘기해서 공부하는...
-
과목은 미적분이고 지금은 기생집 jump풀고있는데 뭔가 불안해서요.. 꼭 해야하는건...
-
경인교대 4칸인데 3개년 합격률이 47프로네 넣어 말아
-
미적2등급인데 커버가능한가요?
-
이게 희망이 있는거야 없는거야 이게 희망이 있는거야 없는거야 이게 희망이 있는거야...
-
나군에 7칸 안정쓰고 가군에 3~5칸 쓸 생각인데 다군에 쓸데가 없음요.. 다군이...
고능아ㄷㄷ