크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
국수 먹고 싶다 4
아악 배고파아ㅛ ㅜㅜ
-
해주세요 목표는 수의대인데 반년으로 될지, 한다면 휴학/무휴반 중 고민입니다. 국어...
-
십ㅋㅋㅋㅋㅋㅋ
-
마늘 먹고 싶다 2
아아
-
연락 얼마나 자주하고 얼마나 자주봄? 원래 친했는데 자꾸 열등감 표출해서 보기 싫어짐 시발
-
요즘이라기보단 그냥 살면서 뭘 해야할지 뭐가 하고싶은지도 모르겠고.. 심란하네요
-
근데 이건 정말 나만 알고 싶은건데..
-
- 기호만 치운 게 원래 답일 확률이 높다
-
심장 아프다 4
요즘 너무 무리했나 따흐흑
-
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 0
https://xurl.es/4stnb
-
봇이지 뭐
-
국수영탐 공부량을 0.5/2/0.5/5 로해서할거임 국어점수는 걍 내 운명에 맡길수밖에없음
-
청정한옯생을살아야지
-
안녕히 주무세요 4
양치햇습니다 5시 알람 맞춰두고 자러갑니다 ㅂㅂ
-
점공 좀 그만봐야하는데 166명 선발, 595명 지원에 점공 328명 중 205등임...
-
현재 선택지가 2개임 27
1.사탐하기 장점: 공부량 적음, 안정적인 백분위 확보 가능 단점: 사탐 선택시...
-
님들은 애인이 13
오티 새터 가면 불안할 거 같음요?
-
질문받을분없나요 38
궁금한거있으면하게
-
잘자요 3
내꿈꿔줄래? 옹?
-
연구실 찾아가면 안됨?
-
사탐런이란? 0
[사탐 the tactics] 1.미련한 짓을 하지 않는다. 2.화학을 선택하지...
-
크아아악
-
이 시간에 8
200명이 살아있네 다들 뭐하고 계심?
-
우리집고양이흰바람벽을좋아해 우리집고양이나타샤를좋아해 그래서 우리집 고양이 백석이야
-
디시인사이드라 했음
-
우리집고양이드릴을좋아해 우리집고양이드릴을좋아해 그래서 우리집 고양이 적백이야
-
항상 국물라면이땡김 ㄹㅇ
-
정석민쌤 커리랑 기출회독용으로 병행할 것 같은데 피램 vs 유네스코 무엇이 충돌...
-
반응 뉴잼
-
다들 인증하고 아무렇지 않게 넘기던데 잘안되나보오
-
-
몸매 조금이라도 드러나는거 싫다거 30도에 후드집업입고 돌아다녔음 요즘은 좀...
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 0
https://xurl.es/4stnb
-
내일은 학원안감 2
그래서 자기 싫음 근데자긴해야하는데
-
4시엔 잔다 2
ㄹㅇ
-
진짜진짜 8
위켄드 노래 다 좋ㅇ은데 이게 레전드임
-
나두선넘질받 17
ㄱㄱㄱ
-
ㅇㅈ 4 6
눈내린서울시립대인증이라네요 진지하게 수목한정 국내대학 원탑 홍보 안해서 그렇지...
-
연대 공대생입니다. 전문직의 필요성을 느끼고 반수할 예정인데 혹시 시대인재 뭐라고...
-
.
-
대성뿐이라 반강제로 승리듣는데 김동욱T 이원준T 완전 궁금함.. 그리고 잠이...
-
나도무물할래 6
나도할래나도
-
5시에 자겠다
-
잇올 뜻 3
Eat All임 음식으로 스트레스를 해소하는 수험생들을 의미
-
나도 무물... 6
ㄱㄱ
-
리젠 뜻 2
Regenerate 임?
-
잇올특 3
친구데려오면 할인인데 친목질하면 강퇴당함 근데 6모 끝나고부터 절반은 친목질하고잇음 ....
-
열등감이 너무심하다...
-
승리 월간지 0
문학 김상훈 듣을건데 비문학은 승리 들을거구 승리 월간지 사는게맞을까? 월간지는...
고능아ㄷㄷ