크리스마스 트리 꾸미기
게시글 주소: 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
-
아 어지러워 0
당 떨어져
-
문학 질문 12
나에서 도화가 웃는다랑 다에서 이슬이 오고 가 의인화까진 맞고 역동적 심상이라서 틀린건가요?
-
12분안에 읽고 플라는 지문을 30분 40분 해설하던데 왜?
-
-
벌레들 캐리하느라 힘든데 같이 힐링하실분
-
해설 상세하게 되어 있는 국어 기출문제집이나 강의 있나요? 2
선지들마다 상세하게 정오 판단을 하는 원리를 알려주고 각 지문이나 선지를 보면서...
-
원래 사문이었긴해서 런은 아니지만 저는 제가 잘하는거 할게요 허수 한명 빠집니다...
-
법규손가락으로 법규합시다
-
정치글 올리면 3
벌점 먹나? 올리고 싶은데
-
새기분 5등급 1
5등급 나오는 분 중에서 새기분 하시는 분 있나요..... 최저런데 강기분 회독...
-
수업때 “그 내가 깊은 생각에 있을때 형제로 활동하시던 분들 중 동생 맡고 있는 그...
-
공부할 짬이 안나오는데... 공대라 수업이 빡빡해서...ㅜㅜ 6모도 못볼거같고 지금...
-
잘자 6
-
한남 0
가든 보추청소
-
메가패스 살 말 0
10만원 할 인 수험표 있고 ㅍ ㅐ ㅅ ㄱ ㅗ ㅇ 유 하실 분 구합니다 ㅡ
-
원에 접한 두 접선에 끼인각, 혹은 반지름 사이 끼인각을 구해야한다 이때 보통...
-
강의수도 그렇고 딱 인강이랑 독학비중이 적절하고 컴팩트함 각 강의별로 말하고자...
-
생각보다 0
옯에 박광일센세 수강후기가 잘 안보이네
-
-
EBS 독서와 문학을 파면 그 효과가 매우 큰가요? 8
EBS 안 했으면 문학 푸느라 30분 걸렸을텐데 EBS 덕에 20~25분 걸리고 그런 느낌으로요?
-
-
아 안가져왓다 0
아쉽지만 오늘공부는 여기까지..
-
우문이긴한데 오르비언들의 인식이 궁금하네요
-
미키 17이 영화판의 한파라는 것을 감안해도 개봉 1달이 지난 지금까지 국내관객이...
-
제가 물리1,2 수업을 하나도 안배워봤습니다 지금 저 공대다니고 공학물리1 수업...
-
마치 내가 진짜 그 사람이 된것같은 기분임 도태한남이 조녜여붕이인척 할 수 있는...
-
내가 탈릅하면 1
이 레어들이 다 풀리게되는건가..
-
집에간다 히히 2
히히
-
벌써 저기에 뜬 꺼릅성~
-
왜? 자기가 알고있는 수학지식을 다적어봐야 하는가? 9
메타인지가 중요하다는데 메타인지는 자기가 뭘알고 뭘모르는지 아는 능력입니다 상당수의...
-
문제자체는 가형 준킬보다는 나형 준킬에 가까웠는데
-
1월 1일에 무안항공....4월 1일에 산불(3월부터 시작됐지만) 우리나라 넘...
-
6모 전에 개념. 뉴런, 기출 끝낼 정도로 하려고하는데 충분한가요??사람들이...
-
동아사 고수만 8
진짜 세기랑 년도 수백개씩 외워야함?
-
고딩때 수학선생님이 하신말임..
-
드디어 성공 6
세시간 기다림
-
이제 만우절 장난 안 치나?
-
포스트잇에 세세한거 다 메모해놔야지 그래야 일을 좀 더 수월하게 할 듯
-
성대나 연대 삼성 계약학과는 석사까지만 하고 취업하니까 0
공대 석박 졸업하고 취업하는 사람들이랑 연봉 차이 많이 남?? 그래서 계약학과...
-
안해봐서 모름..
-
풀이가 씁.. ㅋㅋㅋ 대충 사고과정을 떠올려보면 a[n+1]부터 a[3n]까지 다...
-
암기는 무조건 소리 내면서 하는게 호율이 2.75배 정도 높습니다
-
안녕하세요. 오랜만에 칼럼으로 찾아뵙습니다. 평소에 빨리 읽고 빨리 이해하셔서...
-
푸는데 오래걸리네;;
-
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ너무귀엽다 애들
-
최근 온라인에서 국민연금과 관련한 사진 한 장의 진위 논란이 일었습니다. 사진 함께...
-
1. oxford learner's dictionaries - 가장 많이 쓰는...
-
4월 과탐시작 1
사탐이랑은 잘 안 맞는 것 같아서 과탐 시작하려는데 지금 시작하는 건 많이 늦었나요...
-
다 식엇어 내핏자 아이고
-
막 군대가고 그래서 궁금합니다
고능아ㄷㄷ