크리스마스 트리 꾸미기
게시글 주소: 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
-
일본 타워레코드 청음하는 헤드셋이에요 사진을 안찍어서 짤 주서왔는데 서서 BMTH...
-
진학사 이거 2
관계자가 마음먹고 시도하면 충분히 컷 조작 가능할거같은데 문제있는거 아닌가 애초에...
-
이거 그린라이트인가요? 10
점메추
-
그냥살면되는거아닐까 헬창인생을살아보자
-
수학 원툴 현역 정시파이터 달린다.
-
확미는 했으니 기만 하면 되겠다. 윤곽이 잡히면 그때 결정한다
-
님들 서울공화국 10
어케봄
-
진학사 고대 1
지금 진학사 업데이트 고대 변표 반영된건가요?
-
학과 대부분이 22,23학년도에 비해 추합인원 혹은 비율이 적은데 이유가 뭔가요?
-
-
1년 반 전에 여소받았던 적이 있는데 상대방이 영화보자고 했는데 내가 연락 잘 안...
-
어그로 ㅈㅅ 한지 생윤 세지 정법중 4c2조질려는데 조합추천좀요
-
국어 기출 5
김승리 올오카랑 매월승리1,2,3호에 있는 기출로 기출충분하나요? 아니면 이감으로...
-
낙지 ㄹㅈㄷ네요 고려대 미대 35명 뽑는곳이고 성적 실제지원자중 17등인데도...
-
8명 뽑아서 그런지 칸수가 진동을 하는데 미인증 표본이랑 백퍼 빠져나갈 표본...
-
졸려 으아아앙 4
지금자면 안ㄷ되는데
-
신이 주신 목소리 아닌가싶다 크리스마스 캐롤 들으니 신나네~
고능아ㄷㄷ