크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
부산대 의대를 고민하는데 증원 규모가 그리 크지않고 국립대이기도 한 부산대가 불인증...
-
미적 좀 알려주고 풀어보라하니까 잘 풀더라구요 백통이레벨이 학교에 둘정도 있는데 둘...
-
걍 님들이 과탐하나 모래주머니 없애고 그시간에 다른과목 공부 ㅈㄴ하시면됨 그렇게해서...
-
3합 17 0
삼반수 전적대 이미 자퇴했는데 이성애자 ㅇㅈ?
-
본인만의 공부법이 있나요? 칼럼같은 거 보면 다들 공부법이 있는 것 같기도 한데...
-
시립대 학비 0
싸서 뭔가 손해 보는 느낌 쩌피 부모님 회사에서 학비 내줘서 뭔가 아까움......
-
분명 한 권만 시켰는데 뭐지.. 크리스마스 선물인가..
-
지금 낙지 중경외시 문과 표본 충분히 들어온걸까요? 0
상경계열 앞으로 표본 얼마나 더 들어올까요?
-
나를 위한 선물…^^
-
내일할거 1
엄마랑 전시회 가기
-
국어 문개집 언매 올인원 + 나기출 고전시가 올인원 문학 올인원 + 나기출 독서...
-
원과목에 썩겠다는 애들이 왤케 많음 흠 사탐이 좋은뎅…
-
경희 논술 1
예비1번인데 빠질 사람 어디 없냐… 간절한데
-
그건 바로 세이카 상의 생일
-
아...
-
원나블 특 3
원피스-대략적인 스토리와 기본 설정은 모두가 알지만 애니/만화로 꾸준히 본 사람은...
-
다들 형제자매 있나요? 31
ㅈㄱㄴ
-
-
분명히 어제까진 적정표본수가 34명이였는데 오늘보니까 45명으로 적정표본수가 바뀜…...
-
디모 하시는분 계실까요?
-
할만한 게임없나 20
롤 롤체만 하니까 좀 질리는데 딴겜도 좀 찍먹해보고싶네
-
처음이라그런데 너무 점수 남게쓰는건가 모르겟네요 다들 몇칸조합인지도..
-
원딜 노 ㅇ 1
여기까지만
-
어떤가요 저거 아니면 나군에 성대 4칸짜리 넣고 가군에 7칸짜리 하나 넣을까 고민중임
-
님들아 가군에 a학교 b과 쓰고 나군에 a학교 c과 쓰는거 됨?!?! 나 왜...
-
뻥임뇨
-
과탐 하나도 모름
-
저거 할 줄 모른다고 대학에서 점수를 말도안되게깎는데
-
표본 수준보고 겁에 질려서 런쳤다가 생지옥을 맛봄요 핵형분석부터 염색체 생략하니까...
-
폰 화면은 너무 작은데
-
47이고 문제 하나 잘못봐서 틀렸고 찍맞 1개인데 오늘 다시 풀어보니깐 가산점...
-
이씨발 이거 두문제만 아니었어도 하
-
진지하게 그냥 지방대를 가서 긱사 생활하는 게 맞는 거 같아요
-
난 남잔데 5
왜 여돌 보면 나도 저렇게 예뻐보고 싶다는 생각이 드는거지
-
비유하자면 기하? 근데 기하보다도 재능 안탄다 생각함요 매번 개념 인지하고 유형...
-
주인 잃은 레어 1개의 경매가 곧 시작됩니다. 마박사"잔모래마을에서 포켓몬 연구를...
-
일찍자고 9
크리스마스를 맞아보자
-
현장서바 100을 못 받아서 아직도 아쉬움이 남음 백분위100은 받아봤는데 원점수 100이 없음
-
대충 스토리는 알아서 최종장이랑 정상전쟁만 내일 보려는데 라프텔 끊으면 됨요?
-
메리 크리스마스
-
계실까요??제바류ㅠㅠ
-
확통30번 푸는거랑은 또 다름 미적이 훨씬 재밌음 이감이나 서바 28 30 이런거...
-
블리치 천년혈전 재밌노 14
이거 만화로 볼때는 망한 에피소드라 생각했는데 애니로 보니까 작화빨이 극대화돼서 그런지 볼만하네
-
-
방학때 박종민 미적 99반 현강다니고 고3모고 기준 보통 92~100인데 방학때...
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
재수생 뉴런 0
이번 미적 높3인데요 미적은 시대 단과 들을거고 공통은 인강으로 하려는데 뉴런...
-
선택과목 0
26연고대 공대 언미 사탐으로 뚫릴까요? 사탐런이라 경제 사문 할려고요 잘 맞으면...
-
으흐흐흐
-
올해 수능쳤고 33353 나왔어요 언매 미적 세지 지구 순 입니다 평소에 수학을...
고능아ㄷㄷ