크리스마스 트리 꾸미기
게시글 주소: https://old.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 (+1,000)
-
1,000
-
좀 ㅍ해주세오ㅠㅠ
-
감사합니다 한양대 ㅠㅠ
-
정시 라인 0
언미영생1지1 93/92/2/87/91 수시 다 떨구면 진학사 사려해서 라인 같은...
-
표본분석 시작 0
표본분석 시작하려고하는데 표본분석이 앞 등수 애들이 실제로 어디갈지 보는...
-
낙지 설대컷 조금씩 내려가네요 더 빨리 내려가라~~
-
기만자들
-
으흐흐..
-
인하대 대형과 진학사 서비스 시작부터 6칸 최초합~추합 왔다갔다 하는데 안심해도...
-
아 미쳐버리겠네 1
충북대 의대는 진짜 못믿겠는데 시발진짜 아니 주차장드립을 저거를 어케 받아주지 아제발씨발
-
학교라인 하나차이면... 어떤게 더 좋을까요...?
-
중앙대 기계공학과입니다. 최초 모집인원 68명인데 44등이고 칸수는 6칸입니다....
-
울고있어요
-
에너지공학과 0
고대 융합에너지 , 성대 에너지 등 에너지공학과는 공대 중에서 취업 기준으로 봤을...
-
고대식 점수 2
664.63이었는데 업뎃 되고도 0.01점도 안바뀌었네요..
-
내가 ㄹㅇ 유빈이가 뭔지 궁금해서 텔그를 깔았는데 이게 엄마한테 니 자녀가 텔그를...
-
연대는 진짜 심각하네 13
적정표본수채운건 거의 보이지도않고 대부분학과가 1배수 겨우돌거나 1배수도 못채움...
-
학과 대부분이 22,23학년도에 비해 추합인원 혹은 비율이 적은데 이유가 뭔가요?
-
저도이제대학생이에요
-
진학사 고대 1
지금 진학사 업데이트 고대 변표 반영된건가요?
-
크리스마스 이브 잘 지내세요 메리 크리스마스
-
이거 답 1번 맞져?
-
없이 독서지문 읽을때랑 차이 너무 많이 남
-
어그로 ㅈㅅ 한지 생윤 세지 정법중 4c2조질려는데 조합추천좀요
-
표본좀 오라고 낮춘건가
-
오늘 기능땀 히히
-
낙지 ㄹㅈㄷ네요 고려대 미대 35명 뽑는곳이고 성적 실제지원자중 17등인데도...
-
올해 31명 뽑고 작년 5번 제작년 10번까지 돌았음 추합 총 7차까지 있는데...
-
ㅈ돼지련 살이 빠질 생각을 안 함 방학되고 새롭게 시작하게씀
-
아주대학교 전자공학하고 건국대학교 물리학과중에 어느 곳이 더 낫나요??
-
8명 뽑아서 그런지 칸수가 진동을 하는데 미인증 표본이랑 백퍼 빠져나갈 표본...
-
요약) 금융자산 10억원 이상 부자들이 국내 전체 금융자산의 58.6% 차지
-
독학 질문 2
안녕하세여, 현재 23살 남자인데 중3때 캐나다로 유학가서 공과대학교 3학년까지...
-
나 충북의 싫다고 제발제발 여기좀 붙여줘 제발제발 하나님 부처님 공자님 제발제발...
-
기준이 뭔지 아시는 분 있나요? 실제로 지원할 표본도 빼버리는 것 같은데...
-
과 하나하나 다 개별로 뽑으니까 전부 소수과행 개쫄림
-
중대 기계공학 1
68명 뽑고 저정도면 떨어질까요?? ㅠㅠ
-
3등급 기준
-
뭐지
-
ㅅㅂ ㅋㅋㅋㅋ 6
어제 갑자기 5칸되서 놀랐던 과 오늘보니 1칸되어있네 ㅋㅋㅋㅋ
-
1배수돌리는것도 찾기힘드네
-
5칸에서 6칸 됐는데 좋아해야되나
-
연고 표본이 3
이렇게 적다고??
-
뭔갈해야겠지?
-
Fuck! 23
-
표본 더 들어온거같은데
-
진학사 왜이럼 2
내 6칸 최초합 돌려내 이 시1발 ㅠㅠ
-
이번에 삼기원 붙었는데, 디지스트보다는 지스트랑 유니스트 선호해서 둘 중에 하나로...
-
뚜벅이 되니까 너무 힘드네요
-
본문 씹구라고 제목이 진짜임.
-
나라 망하기까지 얼마 안남았는데 이건
고능아ㄷㄷ