크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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칸 0
18명 모집 19등인데 표본이 아직 46명밖에안돼서… 며칠째 이탈 유입 거의...
-
받아보신분있나…
-
실제론 아닐 수 있음 당연한 소리긴 한데 갑자기 생각남
-
흐흐
-
뭔 아직까지도 적정표본 다 못채운 과가 한트럭이네
-
코엑스 사람 존 나 많음 ㄹㅇ 지금 집인데 그냥 기가 ㅈㄴ 빨리노
-
진학사 안쓰고 원서 넣는사람 많나요?? 글고 등수 변동 지금부터 많이 심한가요??ㅜ...
-
어문계열 질문 0
만약에 어문계열 합격하게되면 해당 외국어 공부 빡세게하고 입학해야하나요?
-
존나할만하다 당장써야지 ㅋㅋㅋ
-
메디컬 ~ 연고라인은 어지간하면 칸수 쭉 유지되는 느낌인뎅
-
메디컬 가야됨 서울대 갈거였르면 애초에 고민도 안 함 ㅋㅋ
-
오늘의 낙지 2
755 입갤
-
커뮤나 군대에서 특정당해도 어차피 현생때메 까먹더라 다..
-
25수능 수학 4맞고 26수능 준비하는 군수생입니다. 현역 때 거의 3은 항상 뜬...
-
스나 마렵네 4
하..
-
수정체를 둘러싸고 있는 모양체근에 힘이 빡 들어가서 수정체를 두껍게 만들고 있기...
-
개념기출 이미 다했고 한두달 놀면서 다 까먹었다고 하더라도 개념기출 빠르게 쳐낼 수...
-
야가미 라이토 0
흐흐
-
문제 하나하나 임팩트 있는건 맞는데 다 기출에 있던거임 이번 세지 동남아, 미국,...
-
n명이랑 당첨 하나일 때첫번째가 뽑을 확률 1/n두번째가 뽑을 확률...
-
성대 공대 0
658.4 ㄱㄴ?
-
진학사 6칸 떨어질 확률 0.7펀데 이게 떨어지겠냐 ㅋㅋ 2
그럴리가없음 ㄹㅇㅋㅋ
-
칸수야 떨어져라 0
나빼고 다 쫄튀하게
-
표본 투투 원투 비율 얼마나됨요?
-
너무 피곤하다 2
과음+타지이동 오늘은 쉬자
-
에휴.
-
하..
-
성대붙여주 0
그만좀 들어와라 나 대학갈래
-
잘잤다 6
-
학교지망 확인도 못하네…? 걍 20개 중에 넣어본건가
-
ㅈㄱㄴ
-
머노?
-
항상 느끼는건데 0
용질을 건데기라고 하고 용매를 국물이라고 하는게 너무 웃김 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
등수 비슷하고 최종컷이랑 가까워졌는데 1칸되네 오히려좋아
-
얘 과외마렵네 머리가 좋아서 과외하면 할 맛 날거같은데 …
-
어디가나요?
-
할거없네 2
심심하네 찐따네
-
피곤해죽겟네 3
메이플 레벨 올려야되는데..
-
굳이 경외시 건동홍이 아니어도.. 급간 높은 문사철 vs 급간 낮은 상경 붙었다고...
-
N=4축 0
깔깔
-
3 받았는데 생각보다 타격이 크네요
-
애니 캐릭터 이름같아
-
글리젠보소 10
다들 놀러갔구만
-
어차피 대학가면 현역으로 온 애+ 현역으로 왔는데 반수하려다 실패해서 복귀한 애+...
-
건양의 지역인재 0
대학어디가로 내신 계산한거 믿을만한 가요? 1점 후반대는 가능한 점수였을까요?
-
어떤 사람이 제시한 의견이나 사람의 행동을 판단할 때 그 사람의 평소 행실에 대한...
-
졸리네 6
오늘 거의 하루종일 잠만 잔 것 같음
ㄷㄷ