크리스마스 트리 꾸미기
게시글 주소: 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
-
잘자요 3
웅냥냥(하품물범이 우는소리)
-
간단해 4
애니프사 호 비애니프사 -
-
일단 난 이제 안함
-
고고링
-
좀만 스트레스 받아도 죽을려 해
-
그동안 속여서 죄송합니다..
-
오늘의 공부인증 6
국: 단과 복습, 강사 주간지 풀이, effect 문학 3지문풀이 수: 어싸...
-
수능때 어디 가셨나요....그리고 영어 커리 추천좀 해주세요...(고정3)
-
자 고고혓 감자깡 먹으면서 적어줄게요 는 아니고 지인선 풀고 적어줄게 5점 만점이다
-
무서워서안햇는데
-
사람들 이거 제일 힘들어 하지 않을까요
-
절대 해달라는건아님뇨
-
호감도 이미지 한단어 56
기기혓
-
이미지(선생님아님) 적어드림 103
-
ㅈ반고 수시 칼럼..? 애피샌츄들이 보면서 비웃을거아냐
-
03이 5수라니 4
틀
-
엑셀 빡빡하구만 1
합성함수가니까 어지럽네 근데문제는좋은듯
-
3월 마지막주 집이 비어서 좀 풀어졌던 감이 있네요 다시 복귀~~^^
-
나보다 여기에 공부 훨씬 더 잘하는 사람들이 많아서 너무 뻘쭘하고 쪽팔림
-
금명이 후배잖아..
-
저는 별로 안좋아함뇨 근데 스낵면은 ㅈㄴ 좋아함ㅋㅋ
-
진짜 연락 늦게 받네 집가면 연락한다면서...
-
홀수해 합성함수 짝수해 적분은 사실상 평가원이 공인한 공식임 ㅇㅇ
-
조금은 즐길 수도 있지 않을까 당장에 화낼 일이 너무 많아서 조금의 행복마저 저축을...
-
입시판 뜬다 3
어휴.. 수능 다시 못 보겠음…
-
드가자~~~~
-
무물보 5
개시다게
-
주식 하나샀다 5
내가 옳은 행동을 한거였으면
-
현역 수학 0
현역 고3입니다. 작수 92(28, 30틀)이고, 평소에 수능이나 모의고사 보면...
-
레어 투기
-
무물보 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? 여기두곳 안정임?
고능아ㄷㄷ