크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
그럼 잡아뒀다가 헤어지면 취소하는거임?ㅋㅋㅋㅋㅋ
-
남자기준으로 결혼하고싶으면 한의대가 맞긴함 둘이 결혼 난이도 차이가 좀 있을걸?...
-
-
국민대 합격생을 위한 노크선배 꿀팁 [국민대25][꼭 가봐야 할 맛집] 0
대학커뮤니티 노크에서 선발한 국민대 선배가 오르비에 있는 예비 국민대학생, 국민대...
-
제가 배웠을땐 고령화로 배웠는데요... 17년도에 고령사회 찍고 12월 23일에...
-
t1 jdg전도
-
지잡대인데 2명이라..
-
그 뉘앙스가 개념에 대한 인식을 재인식하도록 만들기 때문에 틀린게 아니라 단순히...
-
개업건축사 (주 5일 하루 7시간 근무) 월 net 2000+(카페,바 겸...
-
웨이팅이 길구나 1
-
성적인증까지 되어있음 이게뭐노
-
현역 건동홍->재수 의대 가성비 원탑 인생
-
화혁님좃댓네요 21
무슨삶을살아온거임..
-
반갑소
-
이게 머죠.. 3
미제공 이거 머죠..ㅠㅠㅠ
-
듣기로는 수시로 합격이 가능하면 aa 중간에 ab나 bc도 있는 것 같지만 거의...
-
메디컬 편입을 고려 중인데 실패했을 때의 리스크 때문에 자연계열이 아닌 공학계열로...
-
오히려좋은걸?
-
1차합도 못하거나 1차합해도 항상 떨어졌는데… 처음 붙어봐서 너무...
-
숨 쉬기를 좋아하는 사람 << ?? 밥을 하루에 3끼씩 먹는 사람 << ?? 여성인...
-
중앙대 변표 0
변표 발표나고 11점 올랐는데 저만 그런건가요???다들 올랐으려나ㅜㅜㅜ
-
오히려좋아 억울해서 열심히 하게댐
-
탐구보기 싫으면 애초에 탐구 반영비를 줄이던가 병신들인가 좆같네
-
https://youtube.com/shorts/LnihC_H5Qek?si=oWshA...
-
오르비식으로는 못간건가요?
-
잊으면 안 돼 너와 나 마지막이야 이별을 믿지 못하고 위로하듯 불어오는 바람에 잘...
-
지방특징 6
고속도로, 철도 없음 2010년에야 버스탈때 교통카드 사용 가능해짐 20시 전에...
-
예비고3인데 만약에 수능 3등급떳는데 선택과목 저따구면 공대 못가는거죠? 그냥...
-
신검 3급+고졸이라서 상근 소집대상 포함됐다고 문자가 왔다네요....아 ㅅㅂ 부럽다 전 현역인데 ㅠ
-
둘 다 살아봤는데 내가 집돌이라 그런가 스벅 갈때 좀 많이 걸어야 되는것만 빼면...
-
가장 잘 어울리는 듯요
-
이거 게이임? 2
메가에서는 셋다 적정 이상으로 나오는데 진학사로 보니까 개애매함
-
최저 안주는 문화만 뿌리뽑으면 ㄱㅊ은동네긴함..
-
김기병T 과제량이 어느 정도인지 알려주실 수 있나요?
-
라고 합리화중 ㅅㅂ 한문제가 아쉬워지는 순간이다.
-
CGV가도 안방에서 보는거같음 항상 극장에 사람이 10명미만 ㅋㅋ 근데 그럼 적자...
-
기하 꿀잼이네여 9
1단원이랑 3단원 앞부분 개념 배워서 기출 벡터 빼고 이것저것 풀어보는데...
-
오늘 저녁 오픈 예정인 배스트 오르비 마크서버 신청 링크입니다! 해당 구글폼의...
-
암튼 지방은 살아봐야 앎 ㅋㅋㅋ 반박시 님들 말이 맞음
-
제가 가고싶은 과가 있는데 성격상 그 과가 아니면 다른과는 못다닐거 같아요 근데...
-
고2 들어가기 전까지 빡세게 공부해볼 예정인 고1입니다. 올해 산 조정식의 시작해...
-
제발 네이버지도는 봐라... 메디컬이라고 냅다 달려가지 말고 너가 6년...
-
제자 살해 협박에 '방검복' 입은 교사…법원 "협박죄 보기 어려워" 9
(전주=뉴스1) 임충식 강교현 기자 = 특정 교사를 지목해 '죽여버리겠다"는 발언을...
-
수능 성적이 서울대의댄데 내신이 cc 꼴찌랑 격차 20점이상 차이나게 농대 사범대...
-
생일선물 야호 5
시계 케잌 향수 생일파티 온갖 음식 (오마카세부터 등등) 감성템 온갖 청소도구...
-
1학년 1학기 학고->2학기 휴학 후에 반수 실패하면 자진 유급해서 다시 1학년...
-
여캐일러 투척 7
-
성공 마지노선 어디까지라고 생각하시나요??
-
몇십년뒤엔 홍콩 티베트처럼 ㄹㅇ 중국의 자치구가 될거같음 연예인들도 탄핵찬성...
-
크리스마스 투척 0
고능아ㄷㄷ