크리스마스 트리 꾸미기
게시글 주소: https://test.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 (+1,000)
-
1,000
-
14명 뽑아여
-
. . 없습니다
-
유치원때 싱크빅인가 했었는데 하다 말아서 죄다 까먹음
-
낙지 7칸 0
여기서 상승이던 하락이던 변동 가능성이 있을까요?
-
노베 4등급인데 추천좀 오리진vs 봄봄
-
1학년 일반화학 교재 어떤거 쓰나요?
-
수학 공통수학1 정승제 매스디렉터 이미지 세젤쉬 쎈b 개념원리 마플시너지 rpm...
-
정시 인서울 의대면 수학 첫과외 시급 어느정도가 적당한가요 12
제가 인설의 붙는단 소리 아님 그리고 수학 과외 처음 갔을때 뭘 어케 해야할지...
-
4의규칙 난도 0
시준2 40후반부터 갑자기 ㅈㄴ 어려워지노
-
수능에 복수할 생각밖에 없는 수능이 만든 괴물의 삶이면 개추
-
가톨릭vs인천 1
어디가 더 인식 좋나요?
-
곧 코수술할듯 10
드디어 내 코가 높아지는구나
-
이거 진짜 일주일치임? 한 달은 줘야 풀 거 같은데
-
평소에 맨날 보이던 사람 왤케안보임 ㅅㅂ
-
명문대 메디컬 입학은 선진국 국적 취득이랑 비슷한거같다 3
선진국도 빈부격차 ㅈㄴ 심해서 능력이나 운이 부족하면 상대적으로 살기 빡세지고(당장...
-
여친이 공부를 빡세게 하는 타입은 아니라 지금까지 내신5등급 정도 나왔고 모고도...
-
수악 16
미적84점이면 노베는 면제된건가요 중3~고2 수학조교 할거냐고 의뢰왔는데 양심에 가책이 으윽
-
크리스마스 아담은 왜 없음? 진짜 모름
-
. 5
.
-
국어는 피램이나 홀수 수학은 블랭크 영어는..? 뭐하지 무튼 이렇게 생각 중인데 추천 받습니다
-
과외알바를 생각하시는 분들을 위한 매뉴얼&팁입니다. 미리 하나 장만해두세요~~...
-
나도 아직 22살이고 뭐 해본거 없긴한데 이과라면 갈수 있는 길이 넓다고 생각함...
-
소름돋아
-
대학다닐때 주변애들 받는거보고 개부러웠는데 조건되면 신청해보게요 근데 거의 수시러긴 했음
-
탐구 과외하는데 마땅한게 안보여서 아쉬워욥
-
근데 싸이버거를 곁들인
-
3~4수쯤? 자기객관화를 성공하는게 대단하다고 생각해요 재수는 그냥 시간 부족이슈잉...
-
내일 통한의 수학 N제 벅벅을 조질 예비재수생은 개추 3
일단 나부터
-
알바 짤림 7
새 알바 구하는 중... 이브에 짤려서 울적함. ㅜ 학생관리 실수해서... ㅠㅠ
-
스카 어렸을때 보고 포스 지리는 능청스런 빌런인줄 알았는데 과거가 왤캐 추하냐…왜...
-
칸수 7
754 ㄱㅊ을까요 국어 망햇지만 써보긴할듯
-
질받해요 12
취해ㅛ으니 살살
-
부정선거 논란(무근거) 때문에 다시 하는데 참여 안 하시나요 2
https://orbi.kr/00070790467/
-
저보다 후순위인 사람은 어디로 이동하는지 어느 대학을 선택할지 등등을 고민해봤자...
-
그게 나야 바 둠바 두비두밥~ ^^
-
첨부한 그래프가 건대입니닷 건대는 붙는다고 봐도 될거같아서...
-
희망학과 : 경영 ·경제 희망대학 : 서성한~ 중경외시 (대학 높일수만 있다면 과도...
-
ㅠㅠ
-
어휴 ㅋㅋ
-
Team 06 16
근거없이 뭔가 내년 수능은 잘칠거 같으면 ㄱㅊㅋㅋㅋ
-
수능 문학 공부 6
수능 문학 공부 어떻게 해야할까요 이제 고3되는 정시파이턴데 올해수능 언매 94...
-
정시로 28명 뽑고 실제지원자 51명중에 1등이고 전체지원자 202명중에 7등임...
-
의대ㄱㄴ?
-
서울대 경제학부 목표 예비 고3입니다. 학교에 대해 간략히 설명드리자면, 생기부 잘...
-
ㅈㄱㄴ
-
와..... 와..... 와.....
-
아부지는 왜 여기까지 오신 걸까
-
-
화학 인강 0
노베입니다
-
7 6 6 칸 전부 최초합인데 재수생이여서 무조건 가야합니다. 이래도 게이인가요?...
고능아ㄷㄷ