크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
오늘 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칸 쓸 생각인데 다군에 쓸데가 없음요.. 다군이...
-
조금만 잠 안 자고 무리했다고 몸살이 나버림
-
폭등 중
-
괴랄한 칸수 3
이게 뭐임?
-
풀어가야하나요??
-
롤체하기 야식먹기 끝
-
일본에서 맞는 크리스마스 기념 KFC 먹으려고 했는데 0
예약이필요할정도였다니
-
그래 설자전 가자 그래 설자전 가자 긍래 설자전 가자 그라 살자잔 다자 그안...
-
일단나부터
-
ㅁㅌㅊ?
-
왜 크리스마스만 이런 날이 되어버린 거냐
고능아ㄷㄷ