크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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과1이랑 사2 과2 중 어떤걸 하는게 맞을까요? 생지...
-
15살때
-
아 나구나
-
모쏠이라 귀접못함 11
-
형이 알바 끝나고 오면서 사옴 ㅎㅎㅎㅎ
-
ㅎ
-
자각몽시도 이후로 맨날 가위눌리고 귀접당하고.. 근데좋긴했음
-
우와거릴거같은데 명문대아닌가그정도면
-
악몽 꿀때 0
꿈이라는것만 의식하고 눈 뒤집어깔라고 시도하면 악몽에서 벗어나지더라 초딩때까지만...
-
왜 수시에서 도태되어놓고 제도 자체의 불합리함이 어쩌고 웅앵웅거리지 라고 하면 안되겠죠~~
-
고양이 재밌었다 0
정신사나우니까 다시 바꿔야겠넹
-
연애하면서 공부 4
어케 생각 하십니까
-
그만.
-
둘 중 더 좋은거 투표 12
.
-
잘모르겠는데 계속 움직이려고해도 안움직여지다가 갑자기 깸 뭔가 꿈꾼 느낌임 근데 귀신본적은 없음
-
https://m.fmkorea.com/?mid=best&document_srl=79...
-
500cc 3잔 새로 세병 하이볼 2잔 히히헤헤꼴꼴ㅋㅋ루삥뽕
-
가위눌린적은 있는데 귀신본적은 없는데;; 걍 몇초동안 몸이 안움직이는 체험만함
-
몬가몬가임...
-
재수로 수학 올리신분 13
반수하려고 지금부터 공부 시작하려는데 작수 공통1틀(22) 미적4틀(27 28 29...
-
그때도 정시비율 지금이랑 비슷하지 않았나? 교차가 없는데 더 어려울 수가 있음?...
-
컨텐츠비 아껴야제 ㅇㅇ
-
제가 잘모르는데 2
원래 꿈 내용이 정해져있는데 자각몽을꾸면 그걸 본인스스로 바꿀수있음? 원래 좀비한테...
-
요새는 그냥 돈 잘 벌고 나랑 잘 맞는 아내 만나서 적당히 일 스@근하게 하고...
-
가위는 많이 눌려봤는데
-
님들님들그러면 5
이거되는거임? 14명뽑고 36명지원
-
인스타도안하시고 qna도 직접안하시니
-
모벤떠서 다시함
-
수학 문제가 안풀려 11
술만 마시면 머리가 안굴러감
-
연대 빵이라하면 4
컷이 어디라인인거임??
-
ㅇ
-
연애하고싶다 6
안 한지 1년이 다 되어가네
-
티켓팅 때문에 피시방 가야 하는데 어떤 곳은 4060쓴다고 홍보해서 좋은 건지 잘 모르겠어요
-
성격 잘 안 맞으면 굳이 어울릴 필요 없는 거 같아요 4
취준~취직 시기 되니 다들 바쁘고, 여러 이유로 물리적으로도 멀리 간 친구들도 있고...
-
전 이뱃을 못 받네요? 이거 기울어진 운동장이라고 생각해요
-
고대폭 연대빵일줄 알았는데 둘다빵이노 스카이는 허상이 맛다..ㅇㅇ( :ﾟ皿ﾟ)
-
내가뭘했다고정진데
-
계명의 질받 23
계명의 궁금한거 있으면 ㄱㄱ
-
러닝머신 탈 때 1
미3누,주둥이만큼 시간 잘 가는게 없음
-
자면서 공부하고 깨어있을땐 놀면되는데 ㄹㅇㅋㅋ
-
선택장애 왔다 2
ㅠ
-
나도 학원도시에서 초능력 써볼랭
-
와 ㅆ 3
화 1뉴비 1명더생김 미쳐따
-
붙여만 주신다면 미래의 딸내미 이름을 경희나 희경이로 지을게요...
-
근데 별 말 없으심 이왜진
-
90점대 처음 찍어본거였어
-
후하후하
-
정시를 아예 못써요? 아님 정시 합격증까진 나오는데 등록이 안 되는 거에요?
-
전후사정 모르고 한 게시물를 통한 궁금함으로 물어본 건데 정말 죄송하네….
-
가군 동아의 지균 스나하기 전에 그냥 건수 붙는데 쓰고 건뱃 수뱃 달까 생각함 다군...
고능아ㄷㄷ