크리스마스 트리 꾸미기
게시글 주소: https://ys.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
-
ㅇㅂㄱ 4
-
불쌍함 부모님 세대는 수시가 거의 없었고 대부분 정시여서 잘 모르시고 걍 자식도...
-
-
아 대학 좀 보내달라고
-
확통런한 미적러 입니다. 공통 14 21 22 틀이고 미적 27 28 29 30...
-
배고프다 0
진짜 ㅋㅋ
-
애초에 정시에는 수시다떨어져서 강제로 정시로 가는애들도 수두룩한데 얘네도...
-
불가능이라고보내면 안가도되죠?
-
고1 ~ 고3까지 모의고사 12개 + 수능 13연속 1등급이었지만 대부분의 모고...
-
너무 쫄린다 2
설마 f를 받진 않겠지…
-
나만 시간이 멈춘 느낌
-
쩝 0
조용하니 재미가 없고만
-
언제??
-
나만 튕겼음? 3
5분 정도 튕겼는데
-
-
내가 왔다 9
다들 잘 지냈습니까
-
깨있는 사람 1
생존신고 하고가
-
젠장못잤어 2
크아악 버스에서자야겠다
-
헉 1
헉
-
ㅁㅊㅎㄱ ㅅㅍ ㅎㄴㅈ
-
엄 6
um
-
준 0
june
-
식 0
sick
-
쎄하네 4
하
-
고1까지 내신 좋았는데 고2때 완전히 내신 망치고 고3때 정시로 튼 입장으로써 1도...
-
ㅠ
-
그렇게...무한N수의길로
-
-
그렇게 그는 7일 무수면을 하고
-
현역이 그냥 없던데...
-
하고 싶은게 많고 좋아하는 일이 많다는 건 좋은 것 11
가끔은 노래를 들으며 가슴이 뛰고 사업 아이템이 떠오르면 즐거워지고 수능문제가 슥슥...
-
하 0
뒤숭생숭하네 아주 많이
-
다들 굿밤 3
행복하시길
-
꾸중글 6
꾸중
-
겜이라도 할껄
-
기차지나간당 4
부지런행
-
개인적인 좌우명 4
네가 해결할 수 없는 일에 스트레스 받지 마라 그냥 아무 글이나 난사 중
-
국수 먹고 싶다 4
아악 배고파아ㅛ ㅜㅜ
-
해주세요 목표는 수의대인데 반년으로 될지, 한다면 휴학/무휴반 중 고민입니다. 국어...
-
십ㅋㅋㅋㅋㅋㅋ
-
마늘 먹고 싶다 2
아아
-
연락 얼마나 자주하고 얼마나 자주봄? 원래 친했는데 자꾸 열등감 표출해서 보기 싫어짐 시발
-
요즘이라기보단 그냥 살면서 뭘 해야할지 뭐가 하고싶은지도 모르겠고.. 심란하네요
-
근데 이건 정말 나만 알고 싶은건데..
-
- 기호만 치운 게 원래 답일 확률이 높다
-
심장 아프다 4
요즘 너무 무리했나 따흐흑
-
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 0
https://xurl.es/4stnb
-
봇이지 뭐
-
국수영탐 공부량을 0.5/2/0.5/5 로해서할거임 국어점수는 걍 내 운명에 맡길수밖에없음
고능아ㄷㄷ