크리스마스 트리 꾸미기
게시글 주소: 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
-
잘자요 3
이건 진짜임
-
저사실경희의임 6
bl짤단톡방에뿌려서반수해야함 큐ㅠㅠㅠㅠㅠㅠ
-
아 기빨려 4
진따 뮴먐은 과탐하러감
-
연세대>고려대임 1
난 연세대학교 공과대학 다님
-
대전까지가서 6평 볼까요?아님 독재에서 프린트해서? 4
아직 검고 안본 자퇴생인데 그냥 말하면 볼수있다고들 하시길래 제 지역은 진짜...
-
외진 나가서 선생님 먹고싶다
-
그치 벤티야?
-
저격먹기는 가능하더라고요
-
겠냐고 딱봐도 오르비할거같이 생겼는데
-
이전 프사 나눔 3
수요 없는 공급
-
그쵸
-
-
한번 더 할생각임.
-
근데 난 만우절도 아닌데 짝녀한테 고백멘트 ㅈㄴ햇음 4
나 너 결혼식때 깽판칠거야 너 대학가서 남친사겨오면 나 너무 슬플 거 같아 내가 너...
-
동기오빠가 날 설레게 해요 내가 못꼬실 줄 알고? 잡담방에 공개고백 갈긴다
-
미적2틀 0
작수 미적2틀인데 기하로 트는게 맞을까요? 참고로 기하 1단원만 좀 알고 나머진 노베임다
-
-
공산당원786543908위 서열로써 매우 만족하는.
-
왜클릭함 진짜 왜 클릭함
-
-
나 개발팀인데 2
오르비 지켜보고있다
-
만우절 순애 3
대가리 깨져도 순애임
-
-
-
여행 예약 잡으신 분들은 어쩜? 4월에 놀러가려고 비행기 숙소 예약 다 잡아놓으신 분들 여럿 봤는디
-
정해인 비하한 적 없습니다.
-
-
-
뭐가 재밌을까
-
불근불근
-
만우절 질문 받아요 16
전부 반대로나 거짓으로 대답해드려요!
-
일, 십, 백, 천의 고유어는 꽤 알졌지만(각각...
-
-
아 근데 이거 0
닉넴 20일 동안 못바꿈? 아
-
ㅇㅇ
-
자퇴했습니다 1
반드시 존홉의에 들어가고자 하는 결연한 의지입니다
-
ㅋ
-
만우절이네
-
아직 일러를 그리다 만건가 만우절 쌈뽕하네 모두들 밑 오른쪽 하단을 보시오
-
뭐 글쓸거 없나 1
아이디어 딸리노
-
나는 중국인인. 2
너네 빵즈들 대국인 하지 마라 욕. 이 계정은 야동사이트에서 동의한 정보개인 취득해...
-
질문받습니다 22
성적표는 만우절 기념 주작이고 질문받습니다아
-
둘중 1개 인생 선택하라면 어디 택? 기사 댓글보니 나이들어서 돈 많은것보다 자식...
고능아ㄷㄷ