크리스마스 트리 꾸미기
게시글 주소: 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
-
이쁘다고 좋아하진 않으면 얼빠가 아닌게 되지요? 무슨 의미가 있냐 싶다만은
-
주변 소리가 안들린 적이 있나요
-
재즈힙합 좋아요
-
대학 이름빨로 34등급 학생들한테 이름표 장사 하겠잔 거잖아
-
R(x) : x가 현실에 존재한다 E(x) : x가 존재한다 1. ∀x (¬R(x)...
-
ㅈㄴ 만족스러움 내일도 해야지
-
그 말을 기다려주는게 참 어렵구나
-
휴릅이 하고싶네 11
덕코 줄까
-
우우..
-
토요일날 시험본다~~~1종 수동 도로주행 1트 합 보여줄게
-
-
실전개념 들을때 0
문제당 고민시간은 어느정도로 가져가야할까요?? 무조건 답 나올때까지 고민해보고 듣는게ㅡ좋을까여?
-
무언가 잘못됨
-
감정이입됨 슬픔
-
근데 웹툰에다가 순애 어필 엄청하다가 마지막에 ntr하면 캬... 7
독자도 ntr하는 ntr장인 작가 그는 도대체.. 딱 그냥 태그에 #그녀석...
-
친구가 없다 9
아는 사람은 늘어나지만 친구는 줄어드는 느낌
-
369수능 몰아서 해도 되나요 아님 시험 끝나고 기간제한이 있나여
-
양승진 수강생이라,실전개념을 좀 배우고 싶은데 한완수 공통(하)랑 n제 병행하는 거 어떰?
-
그렇더고 삭제하진 않겠어 게이같잖아
-
옯붕이들 잘자츄 11
내 꿈 꼬츄 굿나잇츄
고능아ㄷㄷ