크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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 (+1,000)
-
1,000
-
Team 06 16
근거없이 뭔가 내년 수능은 잘칠거 같으면 ㄱㅊㅋㅋㅋ
-
수능 문학 공부 6
수능 문학 공부 어떻게 해야할까요 이제 고3되는 정시파이턴데 올해수능 언매 94...
-
정시로 28명 뽑고 실제지원자 51명중에 1등이고 전체지원자 202명중에 7등임...
-
의대ㄱㄴ?
-
서울대 경제학부 목표 예비 고3입니다. 학교에 대해 간략히 설명드리자면, 생기부 잘...
-
ㅈㄱㄴ
-
와..... 와..... 와.....
-
아부지는 왜 여기까지 오신 걸까
-
-
화학 인강 0
노베입니다
-
7 6 6 칸 전부 최초합인데 재수생이여서 무조건 가야합니다. 이래도 게이인가요?...
-
10명 뽑는 과라……5칸 추합뜨긴 뜨는데..
-
내일할거 1
아침에 일어나서 공부하기
-
근데 뒤지게 어려움...
-
난 그저 범부일 뿐이다 그러나 26수능의 나는 다를것이다
-
트리 재업 5
https://colormytree.me/2024/01JFMFHHDSQTQCDZT5T...
-
남의 성적인데 1
언매 미적 백분위 88 98에 영물지 등급으로 233(백분위모름)이면 서성한...
-
텔그좀 8
덜믿어도 되나요 49퍼노란색이라서 하는말 절대아님..
-
교대 농어촌 0
공주나 춘천은 농어촌 평백 몇 정도면 들어가나요?
-
수시는 일반고 이과 기준 정시 선택과목은 언매미적과탐(이과) 기준 수시 내신 국어...
-
아웃풋 차이 얼마나날까
-
지2 시험지봤다가 내가 잘못봤나 생각을 한참함 투과목은 절대하면 안되는구나 뼈저리게 깨달음
-
이번주 금요일수업인데 내일은 안올테고 목요일에 오려나?.. 다들 오늘책받은거같던데 금요일수업이면
-
부산대 의대를 고민하는데 증원 규모가 그리 크지않고 국립대이기도 한 부산대가 불인증...
-
미적 좀 알려주고 풀어보라하니까 잘 풀더라구요 백통이레벨이 학교에 둘정도 있는데 둘...
-
걍 님들이 과탐하나 모래주머니 없애고 그시간에 다른과목 공부 ㅈㄴ하시면됨 그렇게해서...
-
3합 17 0
삼반수 전적대 이미 자퇴했는데 이성애자 ㅇㅈ?
-
본인만의 공부법이 있나요? 칼럼같은 거 보면 다들 공부법이 있는 것 같기도 한데...
-
시립대 학비 0
싸서 뭔가 손해 보는 느낌 쩌피 부모님 회사에서 학비 내줘서 뭔가 아까움......
-
분명 한 권만 시켰는데 뭐지.. 크리스마스 선물인가..
-
지금 낙지 중경외시 문과 표본 충분히 들어온걸까요? 0
상경계열 앞으로 표본 얼마나 더 들어올까요?
-
나를 위한 선물…^^
-
내일할거 1
엄마랑 전시회 가기
-
국어 문개집 언매 올인원 + 나기출 고전시가 올인원 문학 올인원 + 나기출 독서...
-
원과목에 썩겠다는 애들이 왤케 많음 흠 사탐이 좋은뎅…
-
경희 논술 1
예비1번인데 빠질 사람 어디 없냐… 간절한데
-
그건 바로 세이카 상의 생일
-
아...
-
원나블 특 3
원피스-대략적인 스토리와 기본 설정은 모두가 알지만 애니/만화로 꾸준히 본 사람은...
-
다들 형제자매 있나요? 31
ㅈㄱㄴ
-
-
분명히 어제까진 적정표본수가 34명이였는데 오늘보니까 45명으로 적정표본수가 바뀜…...
-
디모 하시는분 계실까요?
-
할만한 게임없나 20
롤 롤체만 하니까 좀 질리는데 딴겜도 좀 찍먹해보고싶네
-
처음이라그런데 너무 점수 남게쓰는건가 모르겟네요 다들 몇칸조합인지도..
-
원딜 노 ㅇ 1
여기까지만
-
어떤가요 저거 아니면 나군에 성대 4칸짜리 넣고 가군에 7칸짜리 하나 넣을까 고민중임
-
님들아 가군에 a학교 b과 쓰고 나군에 a학교 c과 쓰는거 됨?!?! 나 왜...
-
뻥임뇨
-
과탐 하나도 모름
고능아ㄷㄷ