크리스마스 트리 꾸미기
게시글 주소: https://ys.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
-
버석버석한 협곡 색깔하며 포탑 디자인도 근본없음 롤이 아니라 걍 롤을 오마주한...
-
재수생임 문학이 박광일이 미쳤다는데 박광일 듣는게 좋나? 작년에 강기분 문학 듣고...
-
첫눈에 반해버렸다…
-
생활과 물리 물리와 사상 세계지학 한국지학 사회문화학 화학과 법 경제화학...
-
25수능 언미영경사 96 93 1 97 99 +설경도요
-
25수능 백분위 87.. 나왔는데 반수 하는거라 시간 관계상 확통런 말고 그냥 계속...
-
어느 포인트에서 안 맞았는지 여쭤도 될까요
-
헬스터디 상대로 6
남자 승패승승승 여자 패승승승승 ㅠㅠㅠㅠㅠ
-
제 불찰이긴 한데... 단대 죽전캠 자전을 넣었거든요 저는 건축학과 지망생이고......
-
1컷까지는 맞는 것 같다 저런 발상을 어떻게 하지? 싶었던 것들 지금 보니 그냥...
-
경희의 컷 0
594 뚫리려나요?
-
라.유.에.게
-
30년뒤 대학 순위는?
-
1. 서울대 광역이랑 자율전공 차이가 뭔가요 2. 설대 광역 사탐 되나요?
-
이거 내년에 2026수능에서 화1 지1 각각 만백 100나올 가능성 있음?특히 화1...
-
화1이라는 제가 사랑하는 과목이 작년에 사망하게 되어서 이과목을 살리는데 조금이라도...
-
당신은 무엇을 버리겠습니까?
-
인생 왤케 힘드냐 설마 식욕 더 늘지는 않겠지 마른비만될텐데
-
절대 남자분이랑 등급합이 같아서 분해서 그러는게 아님 ㅇㅇㅇㅇㅇㅇㅇ
-
지금은 마지막 휴식 타임
-
유베이스니까 아무래도 성공확률 높으려나 글고 여성분 이쁘신
-
마감이 월요일이라 아직 너무 이른 것 같고 동기부여가 너무 안됨... 공부너무재미없어...
-
서성한은 가능거 이과는 안되더라도 문과는 자원 몰빵받으면 가능할지도 생각은 했었는데...
-
병신아
-
저 기쁨 어느정도 오래가나요?? 진짜 저는 경험안해봐서 모르지만세상이 그냥 행복해 보일거 같은데
-
잇올 첫날 .. 5
상담갔는데 오티가 10시? 라고 그 전에 오면 된다해서 걍 7시 50분에 가겠다...
-
서울대 공과대학 광역 지균 391.xx면 고속 빨강인데 이번에 1차합도 어려운 점수일까요?
-
무휴학반수를 하게 되었습니다.. 이대 2합 5 미래인재 전형으로 반수 생각이...
-
가능한거였나
-
이번에 저 네 학과를 쓴 건 아니지만 궁금합니다 노독불중 중에 취업으로 보면 어느과가 유리한가요?
-
수1 1단원 끝!
-
국어노베 커리 6
윤혜정 나비효과 들은다음에 어떤강사분 커리를 타는게 좋을까요? 대성, 메가 다있습니다
-
수능 끝나고 지금까지 먹고 자기만 하니까 부모님이 언제까지 이렇게 살거냐는데 ㅎㅎ...
-
에리카 기계공 vs 상명(서울) 화학에너지공 vs 가천 의공
-
공스타 3
그 플래너에 메모 ? 빈칸 ? 명언 같은거 쓰는곳에 뭐 적어야 하지 명언은 좀 싫은데 노래?
-
콜라도 사와야되나? 근데 엘베 두 개 중에서 한 쪽이 고장남
-
한화 이글스 버러지 야수진 그만 볼 수 있음
-
다시 한번만 돌아와줄래
-
덕코조절 실패했다
-
ㅈㄱㄴ
-
기계 유문 이렇게 2군데만 더 보면 됩니다.
-
거의 매일 올리시는분 찾아요
-
생2를 하면 5
4*3표는 일상인데 허허
-
나 등장 2
헬스터디랑 같이 재수해서 우럿써
-
왜케 조회수가 많지 나 12
뭐지..
-
물2지2하면 없음.
-
잘살고잇나
-
채연이는 팔로우 했고 현수는 팔로우 안 했다 캬캬
-
아직도 하고 있다 야발 사실 위에 뭐 과 구구절절 적었는데 구구절절 적다보니 깨달음...
-
인증은 조금 귀찮으니 수능만 할게요 가볍게 제가 답변할 수 있는 선에서 해보겠슴당
고능아ㄷㄷ