크리스마스 트리 꾸미기
게시글 주소: https://iu.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
-
부끄러워 하지 마십쇼
-
올해 귀차나서 한명밖에 안 썼는데 내년엔 진짜 해달란 분들 정성스럽게 다 해드릴게요 너무 감사해요
-
트리 주소를 올리시면 들어가서 트리 남기거나 트리에 하는것처럼 여기에 대댓글로 남겨드릴게요
-
수업용으로 사려하는데 문제 없겠죠?? 60hz가 좀 걸리긴 하네요... 그리고...
-
드디어 킴… 시퍼런 화면이 여러 모양으로 나오던데 드디어 켜짐
-
목동 메가 재수 1
목동 러셀에서 재수 준비할려고 하는데 괜찮을까요?
-
트리 꼬라지 7
-
-
목표치 채우고싶엉..
-
트리에 등장해써요
-
-
-
현역:23343 언미화생 재수:32311 언미 생윤 생명 제 친구들은 대부분 공부를...
-
인싸들은 어떤삶을 사는거냐
-
애매하단 말이지
-
커플이싫다 2
-
짜파구리가. . . 먹구시퍼요
-
내신 환산점수는 뜨는데 등급은 -표시 된 사람들 뭐죠
-
나도맞팔 5
인터넷 생활이 인생이니까 오르비 인싸도 인싸 아닐까??
-
나무위키에 오르비 이것저것 찾아 보니까 뭔가 엄청 많더라고요. 금색...
-
기차지나간당 8
부지런행
-
여르비 또는 내적 친밀감이 높은 남르비부터 순차적으로 검토할 예정...
-
이분 세상을 passed away 하신 분 아닌가요??
-
물론 1시간 하긴 함.
-
ㅇㅈ 18
근데 다 봤을 것 같은데
-
솔크면 어떠하고 또 컾크면 어떠하리 우리는 수능 끝난 수험생!! 오늘만큼은 즐겁게...
-
연논2차 걸과 0
결과 나옴?
-
호감고닉들 잘 때 몰래 써주면 추합되려나 써드린분들은 장문 보장이긴함...아니면 여기 댓글로도 가능
-
아직 오르비에 내가 덜 절여졌다는 거자나 날 모르는 사람이 많아야해
-
메리크리스마스 10
트리 좋게 써주신 분들 다 고마워요...
-
자야겠다 1
잠깐 편의점 좀 갔다왔다가...흠
-
이거 왤캐 재밌음;;
-
근데 막 파마 했는데 16
보글보글 머리 되면 어캄요
-
아가 취침 14
모두 굿밤
-
어이없는 메시지도 있었고 (왜 저에게 개인적 희망을 적으시는지...) 웃긴 메시지도...
-
문사철 이런데말고 상경(경영,경제)정도 가서 전과나 복전 노리는건 낫배드임?
-
냥대 4칸 0
가군에 냥대 4칸 지르고 나군에 중앙대 6칸 쓰는거 괜찮겠죠? 냥대는 최종컷에서...
-
이거 누구냐 8
저 글 썼다는 당사자는 아니라고 하는 증언을 입수를 했는데 빨리 사칭범 자수하세욧!
-
다 메모했음뇨 미워요..
-
수의대 보면 한의대 성적 나오지만 한의학이 적성에 안 맞아 수의대 오는 사람 몇몇...
-
https://orbi.kr/00070809190 수요 적으면 모집글 안올릴거에요 ㅠㅠ
-
-
-
ㄹㅇㅋㅋ
-
-
오르비 밖은 야바위해.. ,,, 오르비일은 오르비에서만
-
"교회"
-
왤케 웃기지
-
여기에 초대장 올리면 하실 생각 있으신가요?? 수요 있으면 신청 링크 올림
고능아ㄷㄷ