크리스마스 트리 꾸미기
게시글 주소: 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
-
..
-
ㅇ
-
폐경도 완경이라고 해야하는 신세대가 오고 있는데 폐강이라고만 부르는 것은 시대...
-
프변함 5
안녕
-
떡밥뭐임 7
?
-
중력의힘을 거역할수 없으니까
-
게임 ‘전략적 팀 전투’에서, 유닛들은 ‘공격 속도’라는 스탯을 가지며, 한 번...
-
20일은 길다..
-
"실전 모텔"
-
분신술 써서 개념글 올림
-
국가망입니다 하위하위
-
합격증주작 에타주작 학교생활은 망상으로 생각해낸거임
-
근데 덕코 없이 닉네임 바꾼 분들은 20 일을 어찌 참아내려고
-
저 사실 07임 0
.
-
하아으아앗앙 4
그럼 걍 안에 할게 ㅎㅎ
-
전 후 흠... 지피티로 이런 거 됨?
-
퇴근하고 오르비하는중
-
논술을 해야하나 1
어짜피 할꺼면 빨리 시작하는게 낫지 싶으면서도지금 딱 현상황으로는 할 생각이 아예...
-
나중에 다시 올리긴 그렇고.. 걍 알아서 읽을 사람은 읽겠지
-
개허수라 죄송합니다...
-
ㅇㅅ빔 2
뷰르릇
-
문제풀때 유용하게 사용됩니다.
-
나보다 팔로워 적은거보니까 짭이네 ㅡㅡ
-
으으읏 근 하지마~~
-
가보자기
-
안녕하세요 물괴물괴입니다. 오늘은 제가 현역정시설의를 쟁취할 수 있었던 가장 큰...
-
.
-
나쁘지 않을지도..
-
?
-
긴 막대자석을 원형 도선에 넣었다 뺐다 반복해서 전류를 탄생시키는게 뭔가뭔가임
-
자야지 2
-
빨리 피램 쌤도 2D화해줘이
-
어떻게 되냐
-
개인적으로 담요단이고 대수학이나 역학에 거부감이 있더라도 공대를 가는 게 현재의 대한민국에선 맞다고 생각함. 1
일단 출산율이 0.75인데 이것부터 답이 없음. 지금 태어나는 애들은 나중에...
-
난이도 좀 있는 문제집 추천해주세요~
-
심심하면 0
할거를 찾아 세상에 얼마나 할거가 많은데 심심할 이유 하나도없음
-
담요단이네 키타짱
-
힘 다 빠졌어 13
만우절 컨셉 끝
-
계정복구했다 4
-
족발 안와서 일단 다른거부터 먹을려고함
-
속보) 심찬우 쌤이 초 카와이 안경 존잘남이 됐다? 3
헉 캬~
-
아가 자야지 4
모두굿밤
고능아ㄷㄷ