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