크리스마스 트리 꾸미기
게시글 주소: https://ui.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 (+2,500)
-
1,000
-
1,000
-
500
-
심심 1
심
-
What's up, guys? This is Ryan from Centum...
-
농어촌 0
일반으로 건대 인문 쓸 성적이면 어디까지 가능함? 사기라해서 궁금함
-
나 놀아줭 12
심심행
-
궁금하네 저거 cc도 다 뒤지면 흠
-
182명 지원인데 아직도 88명 들어왔네요… 그와중에도 54등이라 이건 포기하는게...
-
벌써부터 깜깜하구나
-
현t 오르새t 양t 좋은분들이 많으니 선택장애가ㅡㅡ
-
닉값 아님
-
사회적 인식 이런거 다 거르고 순수 수능 실력(점수)만 봤을때 보통 3수까지는...
-
-
-
진학사는 칸수를 보세요 10
6칸 게이 5칸 안정 4칸 적정 3칸 소신 2칸이하 스나
-
조발하라 마음 편히 확통하게
-
그게 나여 ㅅㅂ
-
전컴 아닌 공대는 딱히 관심없어서 걍 극 안정 물리학과 썼는데 이미지가 환4보다...
-
삘 와따
-
내신이 좋아서 최저만 맞추면되는데 국어.영어.사탐1개 해서 3합4 맞춰야합니다....
-
최저 맞추기용인데 뭐가 나으련지요
-
문제풀고 채점 후 지문분석서 읽고 해설지읽고 그리고 지우개로 푼거 지워서 며칠 뒤...
-
-
1. 최적t 장: 25수능 정법 풀커리 탑승 후 아주 만족했음 믿음이 감 단:...
-
수1 수2 같이나가는게 좋을까요 아니면 하나 끝내고 하나 하고 그런식으로 해야될까요?
-
공부 안 해
-
안보이는군요 신기해요..
-
재미로만 보세요 0
서울대한테 개기는 "연고대" 연고대한테 개기는 "성균관대" 성대한테 개기는...
-
이원준쌤 강의 들으면서 하루에 1강정도 들어서 하루에 한 지문정도 풀고 전날 강의...
-
오늘 평양냉면 먹엇는데 12
내나이 이십대중반 아직도 슴슴한맛이 뭔지 모르겠다
-
서강대 0
조발해 나도 탈릅하자
-
작년에 재수를 한 제 동생은 강대 조기반 결석으로 짤린 뒤, 동네 독재를 1학기에...
-
발럿다.하면 1시간 20분. 오빠..살려주시오!! 10
범바오빠 날 살려 주시오!!!
-
군대가기싫어요 48
아....
-
학과(전형) 백분위 경영학과(일반) 46 경영학과(법학전문대학원학석사통합선발)...
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 0
https://xurl.es/4stnb
-
식단이 힘든게 2
샐러드랑 닭가슴살?고구마? 다 맛있음 잘 먹음 근데 이제 맛있는거 좋아하는거 참고...
-
확률 20%×5=100%니까 한 문제는 무조건 맞아야하는거 아님?
-
맞팔9 4
잡담태그 잘 안달아요
-
고3때가 마지막이니 그럴 만도
-
김범준 현강후기 2
개씹상타취 개인적으로 최고의 강사같음
-
문학은 감으로 조지고 독서는 그냥 읽고 품 언매는 잘 못함
-
영어 텝스 쳐야하는디 큰일났네요 영어 개못하는디.. 텝스 겁나 어렵던데 4주만에...
-
-
근데 그 어쩔수없는 지점이 너무 ..
-
ㅋㅋ;
-
션티 시작기간 4
6평 80초반(구체적으로는 기억이 안 나요) 9평 97 수능 89 인데 3월부터...
-
기분 젛아요
-
이미지쌤밖에 안들어본 사람이라서 여쭤봅니당 들었을때 어떤가용?
-
몇분부터 잘한다고 봄??
-
2008년에 했던 현자가 간다 편이었는데, 서울대 입학 후에 한 학기만 다니다가...
-
점공 질문 0
발표 나기전까지 계속 들어올수있는건가요? 한참 남았는데 다 안들어오네
고능아ㄷㄷ