크리스마스 트리 꾸미기
게시글 주소: https://io.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
-
인데 행정이랑 정외 중에서 너무 고민되네요 응통도 가능할까요...? 진학사 / 고속...
-
내 영어 3이 문제였음
-
문과...
-
불행회로 등급컷이 맞음
-
진학사 모의지원 분석방법 진학사 글 올라가는지 보려고 그냥
-
일반고 다니는 예비고2인데 이번 여름방학부터 패드사놓고 문제집 스캔뜨고 미친듯이...
-
지방러들이 굳이 인서울을 해야 하는 이유가 있을까요? 공대 기준으로 설연고한서 정도...
-
유빈 근황 4
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ........
-
메가패스 환급 1
왜 환급대상 메가패스를 구매한 이력이 없다고 뜨지? 환급 안되는 메가패스도 있나여?
-
1시간만 기달
-
충사나 볼까
-
-
취업 면에서만 봤을 때 어디가 낫니요?
-
-
퀴즈나 냄 6
곰돌이 푸가 가장 무서워하는 것은?
-
holy......
-
진읽남은 아니죠?
-
-
그런 난이도가 44면...
-
안녕하세요 예전에 오르비를 통해 많은 정보를 얻었는데,아직까지 활발한 것을 보니...
-
지극히 개인적인 일을 가져다가(심지어 본인이랑 관련조차없는일) 아무 연도 없었던 한...
-
흠 0
>>> Tidal >>>>><<<<< Wave <<<
-
설수의 더 선호하긴 함 부모님은 경한
-
6칸 진학 칸수 0
확실하게 붙을까요 ㅜ 몇퍼센트 정도 인가요 14명 뽑습니다..0
-
수학임
-
경찰대랑 비슷한 느낌인가요?
-
ㄹㅇ
-
백호T만 듣고 근육/막전위 도움 되신 분 계신가요? 1
작년에 백호T 한 강사 커리큘럼만 타봤는데 근육/막전위 문제량이 적은 편이었는지...
-
배우면
-
물고기?인지 요정인지
-
있었다가 없으니까 커플망해라 이렇게됨
-
인풋이 좋으니까 아웃풋도 엄청 좋은거 아닐까라는 생각이 듭니다
-
대학 정해지고 그 근처로 과외 잡아봐야할듯 서울에서 한양대로는 걍 안잡힘 찜은 꽤...
-
저번엔 앞자리 앉으니까 막 반말로 무섭게 "돼로가 뒤로가라고~!"이러질않나 오늘은...
-
ㅅㅂ 우리동네만 그런가? ㅈㄴ 무거워
-
-
저 왜 팔로우함 6
뻘글 중 뻘글만 쓰는데
-
진짜괘씸하네
-
무슨 시험끝난날같네 닭장이야 그냥
-
-
ㄴㅈ 볼때 컷 칸수 맹신 하지마라. ㄴㅈ컷 계산함수가 단순하다. 반드시 표본을...
-
음...
-
제곧내
-
이쁜물고기가 너무많음
-
와인먹어야지 7
히히히
-
하루를 잘 보낸 느낌임
-
ㅈㄱㄴ
-
어 형이야 지금 누워있어
-
-
나 아까 1지망 대학교 경영학과 추추추합으로 붙었는데 재수하고 싶음…원랜 전문대...
고능아ㄷㄷ