크리스마스 트리 꾸미기
게시글 주소: 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 (+2,500)
-
1,000
-
1,000
-
500
-
무물보 5
마감입니다
-
영어 풀이 순서 2
듣기할때 21~24부분이 쉬우면 30번까지 품 실모풀땐 어려운경우가 많아서...
-
나도 무물보 해봄 18
질문 0개면 서운해
-
선지 베베꼬는 것 보단 나은ㄷ 스
-
라떼는 대성 타수 박광일 김상훈 전형태 김승리 김민경이었는데 대성 국어 라인업 지리긴했네 ㅋㅋ
-
원인분석 비상대책 마라톤 회의는 안열어야지
-
지난주에 발표함 문항 출제를 배제하는 것은 기본적인 원칙이고 평가원은 그러한 기조를...
-
https://petitions.assembly.go.kr/proceed/onGoin...
-
ㅈㄱㄴ 2등급수준
-
수학은 범부고 화1은 김준 때문에 문풀 칼럼이 의미가 없고 생2는 과목 특성상...
-
다 도망갔나..
-
누가봐도 존예존잘이요 훈녀훈남말고
-
그냥 올오카 2회독 돌리는것도 나쁘지않나요,,? 김승리 수강생분들 조언죰,.
-
0. 사탐을 선택한다. . . . 223. 서울대 합격증을 받는다.
-
그렇다
-
2뜨긴했는데 애매-하네 현역일때 3모 4뜬 거 치고는 괜찮다 싶다가도 문학에서...
-
대부분은 공부에 긍정적인 영향보단 악영향을 더 크게 받을거라고 생각함
-
ㅠ 못풀어써ㅓ 0
쉽다는데 에휴이
-
허수충들 멘탈 박살내면서 그 조각 사이로 개념을 쑤셔넣은 느낌인거지
-
모든과목백분위 88~89나오면 건대상경, 과기대itm? 여기두곳 안정임?
-
1 인증하고 제대로 써보고싶네 흠
-
궁금해요
-
다시 잘될 가능성은 진짜 없을까요… 첨으로 좋아한 걸그룹인데 슬프다
-
평가원 모의고사는 지문이 이제 익숙해서... 교육청 모의고사 3개년치 풀어볼까하는데...
-
아가 자야지 4
모두 굿밤
-
하하
-
-
ㄹㅇ
-
현주넌날믿지
-
점점 뇌가 자극적인것을 안찾기 시작함
-
사탐런 늘어나는게 사탐 응시자들에겐 좋은건가요 나쁜건가요? 8
응시자 수 늘어나는게 좋은건가요?
-
시계랑 쌍으로 24개월 할부 끊고 집에서 쫓겨날듯
-
내신 제외 수능용으로 평가원 기출 1회독 완, 개념형/추론형 모의고사 풀고있는데...
-
시즌 3? 4? 그리고 오프는 중고거래 아니면 못사는거죠?
-
이번 3모 미적분으로 선택해서 2등급이 뜨기는 했습니다만.. 2 턱걸이인데다가...
-
오늘의 공부 7
수학 24 7덮 96(28) 물1 24 4덮 42 (15,19,20) 9덮...
-
맞팔구 1
현역정시설의아님
-
영광을 바칩니다
-
10시 넘으면 집중력 흐트러지네 흠..
-
20세기 거북선
-
못풀겠지만 일단 해봐야지
-
벌점차곡차곡모으고있음
-
자칫 유치해질수도 있는 이여기를 1화만에 모든 주제의식을 오픈해서 최대로 유치해진 애니임
-
어떤가요~
-
다시 대한민국 (새로븐 국민)의 나라 윤석열 국정 슬로건이고 아직도 한티역 같은...
-
미친거아니야ㅈ며칠외박햇는데방오자마자정병도짐
-
독학재수기숙학원을 다니고 있습니다 아마 6모 학원에서 칠 것 같은데 6모성적표...
-
미적만 불내지 좀 말고 ㅠ
-
(였던 것)
-
하 들고 다니기 쪽팔립니다 선생님
고능아ㄷㄷ