크리스마스 트리 꾸미기
게시글 주소: https://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
-
나도? 7
-
메뉴가 별로라 밖에서 먹어야지 흐흐
-
자작모의고사 업로드합니다(수학: 확통 미적 기하 포함) 75
안녕하세요! 어딘가에서 수학을 가르치고 있는 수학강사 손승연입니다. 곧 다가올...
-
나 사실 4
여자 되보고싶음..
-
-
-
남자 번호도 따보고 싶다
-
사회문화 도표 개념만 알고 완전 처음해보는데요 처음부터 윤성훈쌤 M Skill 12...
-
현우진 선생님 n수생 오티에서 엉망이다 그냥 계획세우기부터 다시 배워 라고 하셨던...
-
-
흠
-
6모 접수 마감 0
하이퍼 전일학원 종로 강동pk 싹 다 마감임? 학교 갔다와서 자느라 전화를 못했네
-
사회문화 6시간 공부한 미친놈 됨
-
사실 수의대생이 맞습니다 의뱃 도용해서 죄송합니다 탈릅할게요
-
누구나. 자유롭게활동하는. 오루비. 괜히. 설래는맘. 품고.여사님들괴롭히지맙시다....
-
메가스터디에선 팔던데 대성에는 없나요?
-
옆에 여자가 한명밖에 없어서 못자겠음..
-
-
트러스를 풀다 어싸를 풀다
-
4월, 꽃이 피는 계절. 옯남B는 평소에 관심이 가던 썸녀 혹은 짝사랑녀 H에게...
-
中매체 "한중일, 美관세 충격 대응·반도체 공급망 유지 공감대" 2
한중일 통상장관회의 평가…"美 행동 불확실성에 확실성으로 헤징해야"...
-
모여보자
-
급하게 달려왔습니다
-
ㅋㅋㅋㅋㅋ
-
시대기숙 대기 걸어놓긴 햇는데 러셀최상위반기숙도 ㄱㅊ나요?? 현역 때 시대를...
-
선착순.. 한명.. 베트남 21세 여자에요 부드럽게 대해주실 오르비언 구합니다...
-
one two three I'll be there
-
그 사람인줄 알고 댓 달고있었네요...
-
ㅇㅇ
-
난 그런거말고 학문성교를 원하는데;;
-
누가 닉네임 2
정시일베로 바꿔주면 좋겠다..
-
어제?더프성적표받았네요 11
국어아쉽긴하지만그래도공부한보람이있네요기쁩니다 남은모의고사는더잘봐야겠죠
-
넘 졸리네 2
학교에서 잘 잔 줄 알앗는데 왜 이러지 자야겟다
-
메가커피 가격 오르네 20
에반데..
-
키미니 아이타이
-
11살 여붕이랑 내 쪽지내역이 밝혀지면 곤란한데..
-
30분동안 재밌었다
-
희소성 있는 고닉들만 노린다.
-
최선을 다해서 후회없는 4월을 보내봅시다
-
못 풀겟다
-
맞음
-
하..
-
미라클기상을위한 7
얼버잠
-
자야지 0
늦었다
-
방점은 성조가 아니라 강약을 나타내는 거고 연음도 음운변동임
-
그럴만한 이유가 따로 있었음 남자의 사정임
-
-
경기권인데..신청 빡셀까요?
-
ㅠㅠ
-
으흐흐 6
뭘 기대하신거죠
고능아ㄷㄷ