크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
기구해
-
여론확인해보자 0
신상깐게 나쁘다 ----> 좋아요 ㄴㅇㅁ 똥물 댓글다는 의대 연막 악질 의까가...
-
조금씩 변동있긴한데 대충 이정도선 유지중인데 이거 괜찮아보이나요? 나머지 상향넣고싶어서
-
아니면 너무 후해진건지 그래도이제 1배수는 좀 도네요
-
호시맛치 뱃지랑 0
결속반도 클리어파일 발견
-
개인적으로 1
6칸 2개+1개 스나 7칸 1개+2개 스나가 맞다고 생각함 뭐 미련 없으면 라인 더...
-
설교슬가 2
미하리 선생님이라..쉽지 않을지도 교대는 확고한 사람들이 가는 것 같네요이
-
빵 ㅋㅋ 1
빵나서 합격하면 기분 좋겠다
-
ㅋㅋㅋㅋ 야발
-
성의vs울의 0
성의 울의 둘 다 증원, 부속병원 아니 협력병원(삼성서울,아산)인데 여러분들은...
-
어떤가요? 할만 할까요??
-
ㅎㅎ
-
ㅇㄱㅈㅉㅇㅇ 10
고도의 심리싸움인가
-
170명 쯤 뽑는데 지금 100등 정도임요 얘 믿고 나머지 군 다 상향 지르는 거...
-
연세대 전화추합 1
연세대에서는 전화충원을 안한다는데 4차에서 등록 안한 인원들을 수시로 충원하지 않고...
-
표점(백분위) 국어 132(97) 수학 134(98) 영어2 화학 62(85) 생명...
-
옛날에 라끄리님이 쓰셨던 그 글에 나왔던 그 설문조사를 보면 사람들은 평균적으로...
-
이번에 털린사람은 추호의 동정심도 안드네 댓글로 ㄴㅇㅁ똥물 달리면 기분 좋겠음?
-
평백 62.83 문과 정시 대학 어느정도 갈 수 있나요?
-
홍콩갈까 2
흠
-
ㅈㄱㄴ
-
644 ㅅㄱ 0
다꺼져!!!!!!!!!!!!!!!!
-
환불하려하는데 ㅜ
-
차은우 얼굴
-
카페인 부스트 4
속칭 인간판 TRANS-AM 카페인 음료로 체내 힘을 다 짜내고 힘이 다 떨어지면...
-
도움 도움…. 4
울집 공부에 대해서 개빡센데 나 공부하러 독서실 와놓고 인스타 하는거 혈육한테 걸림...
-
빨리 오세요
-
취업시장선 어디가낫나요
-
아ㅋㅋ 4
444면 하나는 붙겠지ㅋㅋ
-
잊힐 권리를 보장하라
-
656으로 가야하나
-
진학사 보는 놈들도 고여서 막 빵날려는곳 다 써서 폭나고 이러는거아님? 아닌가 강심장 별로없나
-
근데이제 과학적 표기법까지 동원해야 될정도로 미세한
-
4칸 1등 이런거 아니고선 실제로 그렇게 확률적이기보다는 3칸 이하 뚫렸을 때 4칸...
-
ㅇㅇ
-
표본 적은 3칸 0
18명 모집 19등인데 표본이 아직 46명밖에안돼서… 며칠째 이탈 유입 거의...
-
받아보신분있나…
-
실제론 아닐 수 있음 당연한 소리긴 한데 갑자기 생각남
-
흐흐
-
뭔 아직까지도 적정표본 다 못채운 과가 한트럭이네
-
코엑스 사람 존 나 많음 ㄹㅇ 지금 집인데 그냥 기가 ㅈㄴ 빨리노
-
진학사 안쓰고 원서 넣는사람 많나요?? 글고 등수 변동 지금부터 많이 심한가요??ㅜ...
-
어문계열 질문 0
만약에 어문계열 합격하게되면 해당 외국어 공부 빡세게하고 입학해야하나요?
-
존나할만하다 당장써야지 ㅋㅋㅋ
-
메디컬 가야됨 서울대 갈거였르면 애초에 고민도 안 함 ㅋㅋ
-
오늘의 낙지 3
755 입갤
-
커뮤나 군대에서 특정당해도 어차피 현생때메 까먹더라 다..
-
25수능 수학 4맞고 26수능 준비하는 군수생입니다. 현역 때 거의 3은 항상 뜬...
-
스나 마렵네 4
하..
-
고능아ㄷㄷ