크리스마스 트리 꾸미기
게시글 주소: 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
-
표본 상승 안된다...
-
-
공부장소 -스카 수업 -인강, 유튜브 교재 -유ㅂ.. 실모 -작년거 풂(번장당근)...
-
오늘이 몇월 몇일인지는 아시죠?
-
맛도리일 거 같은데
-
고마워요! 4
저 레어 실수로 산거라 맘에 안들었는데 가져가주셔서 고마워요! 차단한 것 같아 볼...
-
사탐은 6모끝나고..?7월까지 기출? 이게 맞는거 같은디
-
현대시가 너무 에바 아니였나요..? 그리고 경제지문 빼고 나머지 독서랑 화작은 어땠죠..?
-
수능 안봐도 되나요? 목공강 못만들거 같아서요ㅠ
-
이게 팩트임
-
이거 왜 진짜있냐 기하 빌드업 보다보니까 나와있네
-
ㅈㄱㄴ
-
집도착 도착 12
씻어야해ㅐㅐㅐㅒㅐㅐㅠ
-
어째서
-
문학 폭망 0
이번 3덮 화작 독서는 1개 틀리고 문학에서 5개 틀려서 88점 나왔는데 문학 공부...
-
뉴르비는 서러워서 울어요
-
과외알바를 생각하시는 분들을 위한 매뉴얼&팁입니다. 5천원 커피값에 미리 하나...
-
이제는 스스로 전문항 정리하고 2회독해야됌 뇌고문on
-
강e분 질문 1
강의 그냥 수특으로 들어도 되나요.?
-
적어도 8월은 돼야 할 듯....
-
솔텍 왔다 2
출발~!
-
흠냐뇨잇 2
흠냐
-
점수 안 나오고 엉망진창일 때마다 얘들 생각나던데 "얘야. 인생은 자기 뜻대로 되는 게 아니란다."
-
우리끼리 놀자 1
모여라 딩동댕
-
기각되면 즉시 복귀해야하는데 11시에 선고하면 들어가자마자 점심시간인데, 10시에...
-
와 팔로워 50 1
저도 당당한 올비 고닉임뇨
-
하 시간 사르르 녹여서 버리고 있네 나레기
-
작년에 몆번 봐서... 이번엔 기출은 스블만 하려했는데 스블 미적 4월말은 가능한가...
-
[칼?럼] 기하런 28
1. 기하런이란? 선택과목으로 미적이나 확통이 아닌 "기하"를 택하는 것 2. 왜...
-
-
미분 가능하려면 케이스가 둘다 미분가능하거나 둘다 미불 아닌가요? 오늘 수업...
-
3점제외
-
시대 김현우 0
이번주 스탠다드 왤케 어려움?? 나만 그런건가…?
-
김범준t 수강후기 중 홍준용 강사님의 사과문과 비교하는 수강후기가 하나 있었음....
-
도전 1일차
-
내일은 수2임 ㅋㅋㅋㅋ
-
레벨업 1
이젠 해야됨 튼튼하게 공식적으로 혁신적으로 준비해야됨
-
-
푸앙이 vs 부 4
싸우면 누가 이길까 재밌는 vs놀이
-
스블 후 기출 0
스타팅 블록에 상당히 많은 기출문제가 수록되어져 있는걸로 알고 있는데 이것을...
-
ㅏㅏㅏㅏㅏㅏㅏㅏ
-
안녕하세요? 기숙학원에 가게되었는데 둘 중에 고민 중입니다.. 혹시 다녀보신 분들...
-
그래서 그런건가 늘 어렵다니까
-
화학화학하악하악 7
더 재밌는 문제... 더 뛰어난 스킬..!! 화학 이야깃거리좀 주쇼
-
내란죄는 타당하다 << 이거라는듯 그래도 헌재 결정은 따르는게 옳다봄
-
기출 다 풀어봤는데 시험장에서 실수 틀만 없으면 틀릴일이 없을거 같은디 실모...
-
내신 n제 0
물1 화1 내신하고 있는데여 기출다 돌리고 (수특도) n제 풀어보고 싶은데...
-
고민상담 좀 10
배고픈데 빼빼로 먹을까요
-
근데 나보고 진짜 중딩같대ㅠ
-
2025학년도 한림대 의대 면접 기출문제(일반.. : 네이버블로그
고능아ㄷㄷ