크리스마스 트리 꾸미기
게시글 주소: 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 (+1,000)
-
1,000
-
수특 물1 3점에서 벽느끼는데 이 길이 맞나 싶다
-
쌤이 수능보기전에 반에서 수능성적 1등은 장학금 100만원준다는 식으로 말했었는데...
-
ㅈ목하는게 꼴보기싫은거지 ㅇㅇ
-
지금 뭘 하고 잇는 거지?
-
정원이 33명이고 분석 대상자가 90명인데 추합이 33등까지라고? 25일인데? 이게...
-
흐흐흐 귀엽구나
-
의,치,약,수 → 과탐 제한있는곳도 있고 가산점 무시못해서 과탐을 하는게 맞다...
-
고인물들이 좋아하는 것 17
1년 만에 왔는데 아는 닉네임들이 뱃지 달고 있는 상황 ㅎㅎ 다들 고생하셨어요~
-
삐딱하게랑 맨정신까지 ㅋㅋ
-
흠...
-
고2까지그랬었는데 어쩌다가 이렇게 냥기공가게되네
-
종합 교과로? 그냥 경기도 일반고 진짜 지극히 평범한 일반고 고점/저점/정배 각각 알려주삼
-
대개 위상이 비슷한 학과들이 있고, 두 학교 식으로 점수가 크게 유불리가 없는데 한...
-
9명 뽑는 과 지원하려는데 1등인데도 불안해서 죽을 것 같아요ㅋㅋㅋㅋ 갑자기 어둠의...
-
내신 3.9 세특에 영리한 아이지만 수업에 관계없는 말을 하여 분위기를 흐림....
-
니 엄마 유골함에 대고 지랄해라 어쩌구 하던데
-
시발 이건 진짜 존나긁히네 이 씨발새끼들아 야이씨발련들아 씨발내가 내년에 씨발 진짜...
-
여캐 일러투척 0
마법사 프리큐어 미라이 데이즈
-
윤 대통령-김건희 여사, '칩거 중' 한남동 관저서 성탄 예배 1
국회 탄핵 이후 관저에서 칩거 중인 윤석열 대통령 부부가 서울 용산 한남동 관저에서...
-
특히 문씨 때 후반에 하루 아침에 동네 편의점에서 일본 맥주가 싹 다 내려가고 했을...
-
어차피 없... .으니까
-
비유를 들어보겠습니다 A년도에 서강대가 학생 건강 증진을 위해 정시에 마라톤...
-
저 아래로 6칸 4명 더 있어요
-
냥냥공공
-
숭숭숭 숭퍼노바 2
숭카이 서숭한 숭경외시 건동숭 국숭세단 광명숭가 숭실숭실 온세상이 숭숭숭
-
아직도 원리 이해 못함 작년도 그렇고
-
기구하다 기구해 올해도 모솔크야
-
그것은 바로 우리 교수님 유튜브… 수학과 전공이 궁금하다면 해석학 영상을 꼭...
-
이 나쁜 새끼야...
-
4칸짜리 학과들만 ㅇㅇ 3칸 붙는건 하늘의 뜻이라 분석해도 의미없고 4칸은 진학사가...
-
원장연 = 문제 푸는 지능은 비교적 높지만 세상의 변화를 읽는 눈이나 자기객관화하는...
-
제곧내 과를 바꿔쓴다해도?
-
그냥 다 짜니까 1
좀 과장해서 어디를 넣어도 빵구나서 붙을거같음 ㅋㅋㄲㅋㅋㅋㅋ
-
궁금한거잇음 0
스나할때 모집인원이 갑자기 늘어난곳을 해야하나여 아님 줄어든곳을 해야할까요
-
진짜 지금 칸수 후해요?
-
생1 맨날 찍관으로 풀어서 1~3등급 진동했는데 제대로 정복해보고 싶은 마음이 항상...
-
N수생이라 무조건 최초합 가능학과를 쓸려고 합니다. 각과마다 표본이 부족해, 비교적...
-
미적과탐 해놓고 통통무시 << 그럴수있음 걔네 공부량 생각하면 뭐 꼴받지만 ㅇㅈ가능...
-
* 자세한 문의는 아래의 링크를 통해 연락 바랍니다....
-
혼자서라도 먹는다
-
표본분석 질문좀 0
이게 결국 업뎃될때를 기준으로 표본을 따지는건데 실지원자보면 표본이 와리가리...
-
중앙대 경영 4칸 890번째정도 되는데 추합이 여기까지 돌까요? 0
다군은 4칸이면 아예안된다는말도있는데 그래서 다군은 무조건 적정으로 적으라고...
-
방어회에 소주 1
가 땡기는군아
-
사설도 아니고 평가원에서 약분했더니 분자에 1만 남게 출제하진 않을 거라고 생각했는데
-
출판 앞당겨서 1월 1일에 출시 뷰탁드립니다
-
할게없다 13
뭐하지 일단 진학사는 이제 그만보고싶음 넷플이나 볼까??
-
오.. 6
크리스마스에도 활활타는구나
-
재수후 1학년 다니다가 군대와서 재도전 결심한 25년 9월전역자 입니다...!...
-
ㅇㅇ
-
디시에서 자기 신상 여기저기 흩뿌리고 다녔나?
고능아ㄷㄷ