크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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 (+1,000)
-
1,000
-
맛있는 음료수 0
닥터페퍼
-
왜클릭
-
저녁먹으러 가기 1
-
제가 나이가 좀 많고 수능에서 커하를 찍기도 해서 이번에 꼭 가야 하거든요ㅠㅠ...
-
그래서 자제함..
-
ㅋㅋㅋ
-
-
수요가 잇음?
-
이 점수로 메디컬 붙을리가 없잖아...ㅠ
-
다시 들어옴 5
춥다..
-
분명히 난 시발점이랑 개념의 나비효과 들으려고 했는데 2
유튜브에서 강민철이랑 조정식이 서로 디스하는거 보고있네…
-
현역 : 설교,경희공 재수 : 수학 지구빼고 씹망 삼수 : 연고공, 한양높공 사수...
-
1. 중대 논술합격 검색 2. 합격되어있음 3. 감격의 눈물 4. 집안도 신남 5....
-
안녕하십니까 저번 글...
-
킥오프 파데했는데 하.. 어려워서 죽고싶음 내가 갸빡대가리겠지 진짜 죽고싶다. .
-
블랙리스트오른적 있음 ㅋㅋ 막 내 아이민가지고 부검하고 메모장에 적어놓더라
-
-
-
문득 생각난건데 12
작년에 저때문에 상처받으신분들께 다시금 이자리를 빌어 사죄드립니다 민폐끼친점 송구스럽습니다
-
오르비 같이 하자
-
뭐지 옆 학교들은 다 있는데 개명 전 이름으로 쳐도 안 나오고 당황스럽다
-
태그에도 없는 20세기 사람이 있다고?
-
정법 표점 0
예비고3인데 정법 이번에 표점도 낮다고 해서 해야할지 고민이네요ㅠㅠ (고2때 정법...
-
논술준비 하나도 안하고 미적만 해서 2문제는 걍 버리고 확통은 무지성 곱해서 더하고...
-
지금 당신의 뱃지는 24
수시로 딴 건가요 정시로 딴 건가요
-
형태변환자 0
야하네요
-
드가자
-
02년생인데 26 볼까 고민중
-
의사선생님은 간에 기름낀거 같다고 운동하라고 하시네요 혹시 그대로 두면 어떻게...
-
저도덕코주세요 2
복권에 덕코꼴박많이했어요…
-
이정도면 안정인가요? ㅠㅠㅠ
-
새르비 하려면 자야 되는데
-
ㄷㄷ
-
재작년에 A대학 에타 가입 후 탈퇴, 올해 B대학 에타 가입했고 정시로 학교 옮길...
-
수2 상 권혁석 이승열 유명환 수2 하 백종석 황지용 최병규 후기 듣고싶어요
-
등수 변화만 좀 보다가 몇명꼬셔서 맛집 탐방 갈듯 다들 맛저하세요!!
-
생명 홍준용 4
어떤분이 쪽지 주신거 어쩌다보니 답변을 정성스레했는데 아까워서 공유함(**제...
-
덕코 구걸 5
2만덕 이상을 복권에 탕진했어요... 덕코 좀 주세요..
-
"모든 것은 에피를 위해" 논술은 에피 안 줘서 우럿서
-
진학사에서 최초 정시 모집 인원이 100명인데 왜 모의지원에서 최초합이 등수가...
-
흔들어라 2
흔듷어라
-
원래 목표도 지리적 인서울만 하면 성공으로 잡은뒤 수능 공부했고 수능 성적도...
-
레인보우 브릿지 3
노을이 이쁘다
-
빅 2
스몰
-
28 30 틀인데 기하 할까요 말까요 공통은 14 20 틀입니다 그래프 잘 못함;;
-
졸업하고 페닥하면서 재수능 설약학사편입 이런거 제외하고 순수하게 의대다니다 반수 or 의합후 쌩재수
-
헉
-
전편 다 보긴 했었는데 다시 보면 그건 그거대로 재밌겠죠? 워낙 띵작이니
-
평가원 #~#
-
난 공부해서 4인데ㅋㅋㅋ
고능아ㄷㄷ