크리스마스 트리 꾸미기
게시글 주소: https://ys.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회독은 다 하고 듣는 건가요? 아님 기출 처음 풀...
-
오늘은 새르비가 2
평화롭네
-
컴퓨터에서도 유튜브로 노래를 광고 없이 계속 들을수 있어!!!
-
나보다 뛰어난 사람이 너무많음..
-
문제는 돈이없다 유럽쪽으로 노려봐?
-
나오자마자 자살마려웠음
-
나 어떡해……
-
9년전 유물 3
-
재밌는일 없나 11
옯비언들 도파민 좀 채워줘
-
오늘은 이제 숙면
-
문학 김상훈 그릿까지 풀 비문학 김승리 언매 전형태 월간지 매월승리 사는게 맞음?...
-
많은 관심 부탁드립니다
-
저는 오르비언들 닉을 기억함
-
분명 안이랬는데?
-
오 뽑았다 1
ㄴㅇ스
-
다들 사이즈 적어주세요 57
남르비면 ㄱㅊ 사이즈 여르비면 컵사이즈
-
10년전 유물 6
-
앱 깔았다 2
자꾸 400 에러떠서 걍 앱 깔음 잘 숨겨놔야지..
-
고2때 담임쌤 생각하면서 딸쳤습니다 그것도 학교 화장실에서요 ....
-
안뇽>< 11
-
반갑슴미다 지구과학을 가르치는 지구과학현샘입니다. 3월 첫째주부터 올려드릴 6종...
-
그렇지..?
-
다음으로 뭐 하는게 좋을까요?
-
https://orbi.kr/00070560417 화1 자작 문제인데요. 올린지가...
-
?
-
혹시 2024년도 연대 약대 이탈인원 좀 알 수 있을까요? 24년도 9월에 공시된...
-
오늘 찍은 사진 ㅇㅈ 11
메타 정상화를 위해.
-
그만해야겠다 아직까지 이상한 글 쓰진 않았는데 혹시 모름…
-
귀접 대충 썰 8
자세히 보이진 않고 아무것도 안보이는상태에서 촉감만 느껴지는데 진짜 ㄹㅇ 너무...
-
열품타 홍보글 2
https://link.yeolpumta.com/P3R5cGU9Z3JvdXBJbnZp...
-
연고 높공 이상이 목표면 사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...
고능아ㄷㄷ