크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
너무 오바인가
-
으흐흐..
-
삼육약이 전통이 있다고 들었는데 어디가 괜찮을까요??
-
하시발 9
유니야 나 좀 믿어봐도 되겠니
-
458 ㅁㅌㅊ 4
-
진짜 예능,방송,음악활동,기타 활동 여러가지 등등 다 참여해서 다른 부문으로 인기를...
-
솔직히 경쟁사 하나만 있어도 서비스 2배는 좋아질듯..
-
테레비에서 하고 있는데 볼 만해
-
학창시절 내신에 손놓고 정시공부해서 내신은5~8등급 모고수능은1~2등급인데 서울대는...
-
광운대 전남대 세종대 10
광운대 건축, 세종대 공과계열, 전남대 기계 다 기숙사 살아야 합니다 님들은...
-
몇 명 더 들어오면 칸수 훅 떨어지고 나가면 훅 올라가고
-
변표 뜨고 6칸 초반에서 5칸 초반 됐는데 불안하다 너무
-
유대종, 강윤구 풀커리 타고 26 수능 도전해봅니당 3
약 N년 전에 현역으로 대학 갔던 아저씨입니다. (그래도 2000년대임...)...
-
보통 이런곳에서 빵나나요? 아니면 마지막날쯤 우수수 들어오나요?
-
30명 넘게 뽑아서 불확실성은 좀 덜한 대신 3칸에서 5칸으로 갑자기 오른 게 계속...
-
좀 ㅍ해주세오ㅠㅠ
-
감사합니다 한양대 ㅠㅠ
-
정시 라인 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명 뽑고 저정도면 떨어질까요?? ㅠㅠ
ㄷㄷ