크리스마스 트리 꾸미기
게시글 주소: 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
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
라떼는... 낙지라고 했는데...
-
연경제 고경제 14
연대식 712 고대식 670 연경제 고경제 둘 다 안정일까요? 선호도는 고경제가 더...
-
국민대 자동차융합학부 Vs 과기대 기계자동차공학과 재수할 생각 없는데 어디가요? 좀 급함
-
벌써 1년 6개월 전이라는거임..
-
동일과기준 고대 6칸 연대 5칸주네 뭐지… 심지어 연대가 좀더뽑는과임
-
이 사이에서 간 보는건 의미 없습니다 대략 500.xx에서 1점도 차이 안나는 곳들...
-
무휴반 예정..
-
경희대학교 유전생명공학과 25학번 단톡방 안내 안녕하세요 유전생명공학과...
-
컴공 재학생분들 컴컴 18
대학 들어가기전에 필요한 공부 몇개만 좀 하고 들어가려는데 뭐해야될지 모르겠어요...
-
ㅇㅂㄱ 0
ㅇㅂㄱ
-
전화추합 기다리는데.. 지금봤는데 휴대전화에 폰번호를 적고 추가 전화번호(1)에만...
고능아ㄷㄷ