크리스마스 트리 꾸미기
게시글 주소: https://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
-
7HChoo
-
영화 추천좀 3
딱 두편 정도 보고 자겠습니다
-
법적으로.
-
올해도 결승 가면 좋겠다 너무 욕심인걸까
-
연애 궁금한 점 2
있으시면 물어보세요 있는 경험 없는 경험 끌어다 정성껏 답장해드림
-
모두 ㅎㅇㅌ합시다
-
알려주시면 만덕
-
걍 평범한 한남임뇨
-
뭐 죄수딜레마 이런거라든지
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 1
https://xurl.es/4stnb
-
지구과학1 망원경 탐사선 종류 특징 다 외워야하나요? 4
오지훈 선생님은 그냥 이런게 있구나 하고 넘어가라는데 진짜 안 외워도 되나요?
-
몇없는기회에요
-
부럽다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
-
점공 붙을까요 0
홍대 중간공 정원 28명뽑고 점공 계산기 돌려보면 엑셀이 예비 39~54번으로...
-
고양이만도 못한것들은 다 나가라
-
제가 현역6 재수5인데 국어만 성적이 안오르거든요.ㅠ 올수능 최소2는...
-
걍 쿠팡뛰어도 됨?
-
12명 뽑는과고 30명지원했어요 지금은 19명중에 10등인데 저보다 높은데 진학사엔...
-
ㅎㅎ 3
ㅣㅣ
-
지듣노 맞추면 500덕 12
ㄱㄱ
-
정시 산출식 알려주세요...
-
좀만 있다가 자야지
-
잘자 4
ㅂㅂ
-
걍 자야겟다 4
하루정돈 굶지 뭐.
-
탈릅합니다.. 14
ㅂㅂ
-
자전 갈거 같은데 반수할거라 어차피 1년 뒤에 다 다른 과 갈텐데 있어도 굳이 가야되나 싶어서
-
얜 이름이 머임 2
-
메타 전환 1
할까요 야식추천
-
이거보고 카레이서 되기로 했다
-
난 동태가 더 좋아
-
걍 정수조건있으면 문제 풀기 싫어짐
-
ㅃ2 잘자 4
..
-
건대vs경희 1
경희는 국캠이고 공과대학 아니고 생명과학대학임
-
님자지큼? 이거 재밌는줄 알았서요.. 저 좀 병신이라 그래요.. 앞으로 조심할게용
-
그래도 나는 거침없이 하이킥…
-
난 당당하게 살아가고 잇어 너네도 좀 당당하게 살아
-
ㅁㅌㅊ? 1
-
난 학벌이라도 높여야겠다
-
ㄴㅈㅈㅋ? 2
ㅇ
-
10초안에 와라 12
10 9 8.. 끝
-
그정도로 했으면 재능 없는 거 인정하고 그만둘 때가 됐다고 성적 떨어졌으면서 무슨...
-
학교인기투표 0
ㄱㄱ
-
서울대 진학사 1차 합불 여부 등록 다들 하셨나요? 3
금요일부터 하려고 했는데 점수공개 페이지에 들어가도 어떻게 등록하는지 알 수가...
-
이거 아는 사람 5
-
그래도 나보다 못생긴 사람 오르비에 한명은 있겠지? 4
한명도 없으면 나좀 슬퍼 ㅜㅠ
-
?
ㄷㄷ