크리스마스 트리 꾸미기
게시글 주소: 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
-
4=사=死 좌파진영 및 위장우파 세력의 '죽음'을 의미한다네요! 죽음은 또 다른...
-
강기본 수국김 0
국어 공부를 한 번도 해본 적 없는 고2 08 노베 정시러입니다… 고1 모고 국어...
-
사탐하고 공대의대 가도 된다고 생각하면 원장연들한테 나쁜말 들으려나
-
나같으면 10번이니까 주기 10인 수열로 하고 선지 세자리수로 바꿨음
-
서울대 10개 만들기
-
수능도 안 보는 30대가 뭣하려고 기웃거림 근데?
-
퇴근 16
힘든하루엿다 진자루..쉴틈없이 일핸네
-
두개로 진행할걸 하나로 간다고 하셨으니 현강과 동일하게 갈수도 있나요???
-
만우절 유우머 4
1. 이 방안에 사과가 존재하지 않는다 2. 이 방안에 존재하지 않는것이 있다 3....
-
0살부터 50살까지 신체적, 정신적으로 성숙하고 50살 이후로는 신체랑 정신이 다시...
-
이기상 선생님 세지 개념 강의 듣고 검정 마더텅 풀고 있습니다 이기상 선생님이...
-
오늘도 왔습니다 2
해설이 필요한 모든 국어기출 알려주시면 해설 영상 업로드해드릴게요.(교사경 평가원...
-
현재 자퇴로 선생님과 상담하고 있는 08년생 입니다 자퇴 후 정시 준비를 할때...
-
안녕하세요 여러분! 유튜브에서 노베주치의 도윤구 채널을 운영중인 수학강사 도윤구라고...
-
의대논술은 내용이 겹치는 감이 있어서 수능수학만 ㄱ
-
수험생활 1년이 안정적이게 될꺼라 생각햇는데국어를 다져놓는게 더 안정적이엿으려나
-
나는 내가 3
빛나는 별인 줄 알앗어요
-
노무현:10시(기각) 박근혜:11시(인용) 이진숙:10시(기각)...
-
더 고이고 난이도에 비해 등급컷 씹창 가속화될꺼 같은데
-
수학은 아예 포기했던 수포자라 신발끈 1강부터 이해안가서 ㅎ 50일 수학 반정도...
-
기대가 됩니다
-
젭알ㅠ
-
냄새로 자리 쫓아내내 와 레전드
-
본가에서 집가는길에 버스 잘못타서 지금까지 살았던 자취방 동네 쫙 지나왔는데 진짜...
-
우우.. 흥이떨어진다
-
연=고>서>=성>한 맞노
-
상반기 모의고사는 난이도가 과대평가되고 하반기 모의고사는 난이도가 과소평가되는건...
-
고인물 N수생분들은 지금 수학 컨 뭐푸시나요? 지금 새로 나오는 컨이라 해도 몇개...
-
아이패드 0
아이패드 잠금하는 어플있나요
-
왤케 어렵지 개털려서 가루 밖에 안 남음
-
4월 목표 0
국어 이비에스 절반+ 언매 기출 끝내기+하프모 4-5세트 수학 시대컨 30세트...
-
-
추천좀 0
ㅇㅇ
-
예비 고1 국어 2
국어 문학을 너무 딥하게는 안하고 약간만 하고 싶은데 인강 추천 받음
-
나도 얼른 대학가서 만우절에 교복입어보고싶다
-
하..큰일났네 2
꿀 쏟아서 강아지가 먹은거같은데 괜찮을까요? 살짝만 먹었는데..
-
어제 학원에서 애들이 의대생들 증원 반대해서 단체휴학 했다는 얘길 하길래 제가 증원...
-
미적은 확통보다 2문제까진 더 틀려도 되는건가
-
힝구
-
열릴만한데
-
모두 밥값이랑 술값이다
-
포병부대 일반병 훈련소때 포병 걸린 동기 있었는데 모두가 안쓰러워했음
-
3모 뭐냐 7
3모 수학 ㅈㄴ 쉬운데 작수 3등급인데 시간 여유있게 96인데여? 29도형은 걍 넘김
-
독서 문학은 정석민 듣고 있는데 화작런 해가지고... 듣기로는 화작은 강의...
-
일단 닥치는대로 다한다 목적이 없어도 된다 보이는거 다한다 책 이해 안돼도 일단...
-
흠
-
오르비에서 똥글 클릭하기
-
송금 받기 전까지 보낸 분은 내역 상세 화면에서 취소할 수 있어요. … 방금,,,...
-
-
28번 3분컷이네... 미적은 3년을 박아도 28맞힐가 말까인데
고능아ㄷㄷ