크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
곰돌이 푸가 가장 무서워하는 것은?
-
holy......
-
진읽남은 아니죠?
-
-
그런 난이도가 44면...
-
안녕하세요 예전에 오르비를 통해 많은 정보를 얻었는데,아직까지 활발한 것을 보니...
-
지극히 개인적인 일을 가져다가(심지어 본인이랑 관련조차없는일) 아무 연도 없었던 한...
-
흠 0
>>> Tidal >>>>><<<<< Wave <<<
-
설수의 더 선호하긴 함 부모님은 경한
-
6칸 진학 칸수 0
확실하게 붙을까요 ㅜ 몇퍼센트 정도 인가요 14명 뽑습니다..0
-
수학임
-
경찰대랑 비슷한 느낌인가요?
-
ㄹㅇ
-
백호T만 듣고 근육/막전위 도움 되신 분 계신가요? 1
작년에 백호T 한 강사 커리큘럼만 타봤는데 근육/막전위 문제량이 적은 편이었는지...
-
배우면
-
물고기?인지 요정인지
-
있었다가 없으니까 커플망해라 이렇게됨
-
인풋이 좋으니까 아웃풋도 엄청 좋은거 아닐까라는 생각이 듭니다
-
대학 정해지고 그 근처로 과외 잡아봐야할듯 서울에서 한양대로는 걍 안잡힘 찜은 꽤...
-
저번엔 앞자리 앉으니까 막 반말로 무섭게 "돼로가 뒤로가라고~!"이러질않나 오늘은...
-
ㅅㅂ 우리동네만 그런가? ㅈㄴ 무거워
-
-
저 왜 팔로우함 4
뻘글 중 뻘글만 쓰는데
-
진짜괘씸하네
-
무슨 시험끝난날같네 닭장이야 그냥
-
-
ㄴㅈ 볼때 컷 칸수 맹신 하지마라. ㄴㅈ컷 계산함수가 단순하다. 반드시 표본을...
-
음...
-
필기용, 애니관람, 문서작업(노트북있긴한데가끔탭으로 문서작업 하고싶음, 노트북...
-
제곧내
-
이쁜물고기가 너무많음
-
와인먹어야지 7
히히히
-
하루를 잘 보낸 느낌임
-
ㅈㄱㄴ
-
어 형이야 지금 누워있어
-
-
나 아까 1지망 대학교 경영학과 추추추합으로 붙었는데 재수하고 싶음…원랜 전문대...
-
화2 농도변환 0
m M m % 공식 외워야되나요? 화1에서 % M 공식은 외웠는데
-
님들 머함 7
오르비말고
-
불후의 명강 작년이랑 책 많이 바꾸ㅕㅆ나요? 다시 사야할까요?
-
개좆됐다
-
라고 밖에 추측이 안 되는데 진짜 뭐지
-
페북처럼…
-
어제부터 집에만 있었어요
-
???
-
웬만헤서 연대 폭발 고대 펑크일득
-
올해 여친없는 옯붕이들은 내년엔 무조건 생길거야:)
-
진학사에 얼마나 들어올려나… 무서운데
고능아ㄷㄷ