크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
남친 ㅇㅈ 6
-
지금은 염색같은거 안하지만요? .
-
질받 5
식물 좋아하는 대학생임뇨
-
한 약 수 다 붙었습니다 이것저것 굉장히 많이 고민해봤습니다 현재 업계 평균...
-
크리스마스 기념 9
질답 메타 굴릴게요! 질문 안해주면 잡아먹을거임뇨.
-
나무위키에 오르비 이것저것 찾아 보니까 뭔가 엄청 많더라고요. 금색...
-
프사 색깔?질문!! 12
보니까 금색 파란색 은색 동색 이렇게 있던데 이거는 어떻게 설정할 수 있나요? 저도...
-
실제로 본인 얼굴 사진을 올리는 사람이 있나요?? 한 번도 못봄
-
기만하러 온건가..
-
교수님 안 주무세요?? 기습 계엄도 아니고 새벽 발표라뇨
-
-
ㅇㅈ 5
잘 찍었죠
-
저눈 피방가서 놀다가 저녁에 외식해요
-
아니 근데 12
이 사람은 뭡니까 제가 왜 저아저씨와 좋은사랑을... 아 할아버진가
-
수시광탈해서 정시로가야는데 54346이 진학사 쓰는건 돈 아깝나요? 7
그냥 지잡대 성적이니가 진학사 11만원결제해서 쓰는거 걍 돈낭비일가요? 그래도 쓰는게 나을가요 ㅜㅜ
-
리미쨩 코스했다 2장 올렸는데 또 1장만 올라가면 개빡쳐서트월킹출거다
-
진짜 세상이 날 속이고 있는 게 분명해
-
메타 열어본 사람으로서 키 메타가 ㅈㄴ 무서움
-
메리크리스마스 10
트리 좋게 써주신 분들 다 고마워요...
고능아ㄷㄷ