크리스마스 트리 꾸미기
게시글 주소: https://i9.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
-
라.유.에.게
-
30년뒤 대학 순위는?
-
1. 서울대 광역이랑 자율전공 차이가 뭔가요 2. 설대 광역 사탐 되나요?
-
이거 내년에 2026수능에서 화1 지1 각각 만백 100나올 가능성 있음?특히 화1...
-
화1이라는 제가 사랑하는 과목이 작년에 사망하게 되어서 이과목을 살리는데 조금이라도...
-
당신은 무엇을 버리겠습니까?
-
인생 왤케 힘드냐 설마 식욕 더 늘지는 않겠지 마른비만될텐데
-
절대 남자분이랑 등급합이 같아서 분해서 그러는게 아님 ㅇㅇㅇㅇㅇㅇㅇ
-
지금은 마지막 휴식 타임
-
유베이스니까 아무래도 성공확률 높으려나 글고 여성분 이쁘신
-
마감이 월요일이라 아직 너무 이른 것 같고 동기부여가 너무 안됨... 공부너무재미없어...
-
서성한은 가능거 이과는 안되더라도 문과는 자원 몰빵받으면 가능할지도 생각은 했었는데...
-
병신아
-
저 기쁨 어느정도 오래가나요?? 진짜 저는 경험안해봐서 모르지만세상이 그냥 행복해 보일거 같은데
-
잇올 첫날 .. 5
상담갔는데 오티가 10시? 라고 그 전에 오면 된다해서 걍 7시 50분에 가겠다...
-
서울대 공과대학 광역 지균 391.xx면 고속 빨강인데 이번에 1차합도 어려운 점수일까요?
-
무휴학반수를 하게 되었습니다.. 이대 2합 5 미래인재 전형으로 반수 생각이...
-
가능한거였나
-
이번에 저 네 학과를 쓴 건 아니지만 궁금합니다 노독불중 중에 취업으로 보면 어느과가 유리한가요?
-
수1 1단원 끝!
-
국어노베 커리 6
윤혜정 나비효과 들은다음에 어떤강사분 커리를 타는게 좋을까요? 대성, 메가 다있습니다
-
수능 끝나고 지금까지 먹고 자기만 하니까 부모님이 언제까지 이렇게 살거냐는데 ㅎㅎ...
-
에리카 기계공 vs 상명(서울) 화학에너지공 vs 가천 의공
-
공스타 3
그 플래너에 메모 ? 빈칸 ? 명언 같은거 쓰는곳에 뭐 적어야 하지 명언은 좀 싫은데 노래?
-
콜라도 사와야되나? 근데 엘베 두 개 중에서 한 쪽이 고장남
-
한화 이글스 버러지 야수진 그만 볼 수 있음
-
다시 한번만 돌아와줄래
-
덕코조절 실패했다
-
ㅈㄱㄴ
-
기계 유문 이렇게 2군데만 더 보면 됩니다.
-
곧 출시될 2026 ebs 수특 문학 작품을 평가원에서 묻는 지점만을 중점적으로...
-
거의 매일 올리시는분 찾아요
-
생2를 하면 5
4*3표는 일상인데 허허
-
나 등장 2
헬스터디랑 같이 재수해서 우럿써
-
왜케 조회수가 많지 나 12
뭐지..
-
물2지2하면 없음.
-
잘살고잇나
-
채연이는 팔로우 했고 현수는 팔로우 안 했다 캬캬
-
아직도 하고 있다 야발 사실 위에 뭐 과 구구절절 적었는데 구구절절 적다보니 깨달음...
-
인증은 조금 귀찮으니 수능만 할게요 가볍게 제가 답변할 수 있는 선에서 해보겠슴당
-
시험 한 2주전에 러셀 홈페이지에 신청하는거 뜨나요
-
음악듣고 싶은데 유튭 프리미엄 안써서 다운을 못받는다. 열품타는 쓰고있음
-
??:님 공시 본다면서요 아직 탈릅 안하셨네요 "다시 한번 읽어봐 주십시오....
-
수학 풀 때 무의식적으로 멍때린다고 해야하나 아무생각 없이 가만히 있을 때 있는데 어떻게ㅜ해결함?
-
한지:인문지리가 더 어려움 세지:자연지리가 더 어려움 이건가? 한국보다 전세계가...
-
생명 OX표 사탐에도 나오나?
-
물리 개 씨발련아!!!!!!!!!!!!!!!!!!!!!!!!!!!
-
알바 개바빠요… 4
월수목금일 다 알바임… 여기에 일주일 두번 체육관 가고 두번정도 약속만 잡혀도 ㄹㅇ 죽음인듯
-
그냥 대충 공부하면 수시로 중앙대는 가겠지~하면서 존나 놀았음 그러다 올해 상담때...
-
예비고3 설날 2
공부어쩌고 저쩌고 할건데 그냥 주변4년제만 가고싶다고 하고 대화중에 좀 덜...
고능아ㄷㄷ