크리스마스 트리 꾸미기
게시글 주소: https://h.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
-
ㅁㅊㅎㄱ ㅅㅍ ㅎㄴㅈ
-
열등감이 너무심하다...
-
수학 문제가 안풀려 11
술만 마시면 머리가 안굴러감
-
의대 12
과탐1 사탐1 조합 힘듦?
-
ㅇㅈ 7
대 가 천
-
난 ㅅㅂ 왜 못들어봤지 분명 좋은 공교육 강사인데 드릉드릉이라는 말 쓰는게 조금...
-
외모 영역 1등급이 4%라 생각하니까 그냥 까마득해보임 ㅅㅂ1등급 왤케 어렵냐
-
수능55543 12
한양대,지스트 학종 ㅋㅋㄹㅃㅃ
-
가 접니다 ㅎ 올해부터 오르비클래스 국어 인강으로 복귀합니다 (지난 몇 년간은...
-
질문이 창의적이면 덕코도 ㄱㄴ
-
-
내 글에 훌리들 총집합한느낌 막 싸우진 않아서 글은 냅두고있는데 이러다 싸우는거 아니겠지
-
나오늘여행감 21
일본갈거야 헤헤 기만 ㅈㅅ 근데 수능 좃박아서 기분 ㅈ같음 우럿서
-
왜 일반하고 점수가 다르요?
-
오랜만이다 1
아침의 거리
-
수학은 아닌 것 같음 찍맞은 없는데 내 실력보다 부풀려 나온 것 같아서 찝찝함
-
내일 중학교 친구들이랑 17
방방이타러감
-
울고 있었다면 다시 만날 수 없는 세상이 멋지지 않았는가
고능아ㄷㄷ