크리스마스 트리 꾸미기
게시글 주소: 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
-
ㅈㄱㄴ
-
-
잔다 9
안녕히 주무세요
-
이번주 목표 0
미친개념 수2 완강
-
자러가요 9
요가러자
-
기만자였네 ㅆㅂ 나만 진짜 도태남이지
-
난 어딜가나 호감인데 10
ㄹㅇ인데
-
유혹받았는데 내가 거절했어 한순간에 남같이 돌변하더라 너무 힘들어 지금도 울고 있어...
-
변형 문제 얻을만한 곳 여러 추천해주실 수 있나요..?
-
1식을 미분하면 정답이 나오는데 2식을 미분하면 정답이 안 나옵니다 왜 2식을...
-
신뢰도 팍 떨어지네
-
잇올 6모 신청 0
페이지 드가면 뭐 써야댐요 이름 전번 신청센터 이거만 물어봐요?
-
관리형을 다녔는데 잇올같이 빡센 곳이 아니었는데도 잘되는 날은 관리체계 덕에 더...
-
https://m.dcinside.com/board/dcbest/292946...
-
안녕히 주무세 3
지 말고 밤새야지 어디가노
-
추가적으로 이정도를 풀수 있을정도면 수능때 1은 걱정 없을까요?
-
정직한 제목
-
국어 언매 n제 추천해주세요
-
일반고 내신 4.3x 희망 학과의 권장과목은 다 이수했으나 그 권장과목의 등급이...
-
응응
고능아ㄷㄷ