크리스마스 트리 꾸미기
게시글 주소: https://app.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
-
받은지 15분도 안 됐는데 여기까지 먹어버림 스벅 푸드중에 제일 맛있는듯
-
그런거 모르겠고 재수생 삼수생 수능 지박령들 다 죽이고 한번에 대학갈 팀 07 레츠고 ㅋ
-
건동홍 낮과~국숭 높과 성적인 사람보고 유베뽑는다고 뭐라하는 건 재밌긴하네
-
얼마나중요함? 학과가
-
노베 성적표 인증<<클릭해보면 11221 이런거 나온게 한두번이 아니라서
-
이런 것도 보고 싶긴 함뇨
-
이번에는 커리 갑작중단되지는 않겠지?
-
시대인재 물리 0
시대인재 현정훈 선생님 라이브 수업 5주차 자료에 시대인재 기출문제집이 포함돼있던데...
-
이게 가능함? 6
9평->수능 이라는데 국어황 귀신이라도 들어왔나
-
현우진 커리 0
보통 시발점 듣고 바로 수분감으로 넘어가는 건가요..? 개념 1번 돌린 수준에서는...
-
분명 작년엔 유베 뽑으라고 울부짖었는데 뽑으니까 이럴 거면 왜 뽑냐니...
-
8시까지 과외인데 2회연속 2시간 늦은 학생때문에 무료 2시간 연장수업중이란거임...
-
휴 다행이다 헬스터디 남자애한테 현역수능 기준 수학영어만 따였네
-
얘네 둘이 ㅈㄴ 맛있음... 근데 둘 다 단거라 같이 먹으면 좀 과하긴 함
-
ㅋㅋㅋㅋ와
-
결국 6수 해서 붙긴함 근데... 점수가 올라서 붙은게 아니라 교대가 낮아져서 붙음...
-
수학 영어 탐구는 ㄱㅊ아서 인강들으면서 독학중임 참고로 나 관리형 독서실 잇올...
-
동국 경영정보(산공으로 전과 혹은 복전 할 듯) 과기 산업정보시스템 숭실...
-
시즌3 라인업 봤는데 이게 헬스터디 원래 취지가 맞나?... 4,5등급 그 이하의...
-
(사실 안넣어도 망함)
-
저도 닉변추천좀뇨 20
사실 11일이나 남음뇨 하아
-
여자 패패무패승 남자 패패패패무 일년 동안 열심히 해서 역전한다
-
그래도 아직은 하차소식 없던데
-
이영수 기출분석까지 따로 풀필요는 없나요? 해설이랑 맛도리라길래..; 그냥 한명...
-
10대 후반부터 30대 초반까지 수능 공부에만 매몰(치곤 공부 좆도 안하지만 아무튼...
-
빨리 해줘
-
과탐1이랑 비교했을때
-
건대가는 제가 할 말은 아니네요 죄송합니다
-
와..
-
헬스터디 올리고 반응 무조건 보고 있을듯 아님말고
-
이러다 뒤지는거 아닌가 모르겠네
-
나였어도 나랑 성적비슷했는데 어느순간 따이면 열등감 느껴져서 못볼거같아
-
어허
-
아예 최상위권 뽑아다가 수능만점 목표로 공부시키는게 더 재밌었을거같은데ㅠ 노베라...
-
1컷부근은 진짜 가성비goat인데
-
작년엔 침울해서 안봤는데 재밋다 이채연 윤현수 화이팅!!
-
오늘 국어학원 들어갔는데 여긴 안될 것 같다는 느낌 쎄게 받음? 다른 과목 학원은...
-
안보이네 그 양반....
-
가는거 당연한게 아닌데 오르비는 역시 다른가 다들 그냥 간다는 분위기네
-
아. 7
인생 최거 몸무개 갱신함..
-
노베를 살
-
이중전공으로 경제학 선택 생각중이면 1학년 때부터 경제학과 강의 들을 수 있나요?...
-
다들 고우신데 흠
-
10년 넘게 9급 공시에 올인한 노량진 고시낭인 출연 공부 대충 하는 모습에...
-
화2 컨텐츠 2
오늘 베테랑의 개념완성(고성용) 인강 끝남 개념만큼은 완벽하다고 할정도로 복습도...
-
학교다닐때 같은반이었으면 가슴앓이 좀 햇을듯 볼살빵빵,,
-
어떰?
-
유베이스를 상위권~최상위권으로 올리는 게 답이다
-
국어잘하는 애 뽑지.. 국어 2등급이고 나머지과목 4~5등급 이래야 재밌을텐데
-
가능성은 있어 보임... 오리지널 시리즈 계속 하면서 외전격으로 리트나 공시 수험생도 굴려보고...
고능아ㄷㄷ