크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
유빈아카이브 같은 자료방 더 없냐 추천 좀 해줘라
-
그런게 가능할까
-
양악 윤곽 눈 코 이마거상 지방흡입 드가자 ㅋㅋㅋㅋㅋ
-
요즘 소확행 1
내 몸이 버틸 수 있는 최대 따뜻한 온도로 샤워할 때 창문 열면 영하의 한기가 후욱...
-
아줌마 왜 좋아하냐면서 씨부랄 것들
-
언매 커리 누구 들을까. 언매는 김동욱.
-
우와 와 와 5
K~~~C~~~
-
공익무조건 뜰거같은데 이미 망한 인생 군대보내서 뭐하게...
-
역시 대 이 유 1
최강 동안
-
맞팔구함 2
ㅇㅈ은 조만간 할게요
-
ㅇㅈ할까? 6
말까
-
이거 봐 5
사진 마다 다르게 나옴 1.5점씩이나 차이나는데
-
듣기전에는 커뮤에서 어렵다길래 무슨 고능아 전용 빡쎈 강의인줄 알았는데 초반...
-
ㅇㅈ 7
대 가 천
-
난 ㅅㅂ 왜 못들어봤지 분명 좋은 공교육 강사인데 드릉드릉이라는 말 쓰는게 조금...
-
평범하게만 생겼더라면... 평범한 지능만 가졌더라면...
-
쌍수해볼까 13
쌍수 뭔가 해보고싶네
-
-
그만하라고 했다 !!!!!!
-
제2외로 한문 할만한가
-
원래 잘했던 사람들 말고 등급 낮았다가 높아진 분들중 답주시면 좋을거같아요 저처럼...
-
-
. 4
. . . . 조회수 확인용 도대체 왜클릭…?
-
..... 4
-
나도 여르비 할래 헤응
-
바코드닉임 ㅎㅎ
-
왜 일반하고 점수가 다르요?
-
골때리는 걸 좋아하는 성격이라서가 아니라 관심받고 싶어서 그럼 보기싫으면 조용히...
-
킹치만 고닉들이 아니면 댓글을 안달아주는걸…
-
잇올이나 러셀같은데 15
담배펴도 되나용???
-
추억의 장소 0
군수 2학교
-
조용히 무시하면 됨 알아서 사라질 수 있음
-
갑자기 든 욕망인데 좋아하는 노래랑 장르 대표 아티스트와 매력포인트같은거 쭉...
-
진짜 하면 계정 폭파되서
-
커뮤의 장점 4
현생과는 다르게 참고 살 필요가 업다
-
ㅇㅈ 재밌겠다 4
ㄷ
-
어삼쉬사 난이도 0
수분감 풀기전에 슥ㄱ슥 풀만함?
-
ㅇㅈ 10
9점은 처음 떠보는데 ㅋㅋㅋㅋㅋ 맨날 8점 받다가..
-
근데진짜궁금햇단말야.
-
싹다 술마심? 나보다 더마신거같애
-
ㅈㄱㄴ 강도가 셀수록 좋아요
-
내신 확통하는데 0
이미지t 세젤쉬 + 미친기분 시작편 + 마플시너지 + 시험직전에 족보 <<< 이...
-
나도 손 ㅇㅈ 1
-
생1은 1컷~2등급 중간? 언저리 실력이라 그냥 스테이 해야할거같고 지1이...
-
정실은 시로코 14
키보토스 최고의 미소녀
-
꿀잼일텐데
-
..
고능아ㄷㄷ