크리스마스 트리 꾸미기
게시글 주소: https://m.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 (+1,000)
-
1,000
-
물표 불표 1
물변환표준점수와 불변환표준점수로 판단하는 대략적인 기준이 어느정도에요??
-
질문은 심심해서 올리긴하는데 의견은 현직에 있으신 분들 의견 듣는중 이게 맞아~
-
뭐있음?
-
내 저녁 ㅠㅠ
-
수만휘에 정시성적으로 어디갈수 있냐고 물어보면 안됨 7
자기가 갈수 있는 대학에서 한 라인은 내려서 말함 일부러 그러는지 모르겠는데 기준이...
-
내신 & 수능 모두 준비하려구 하는데 오지훈 강의가 너무 많더라구요 물화는...
-
우웩 오늘 잠 못 자는 게 여자 때문이 아니라 음식 때문이라고?
-
잘생기고 머리 좋고 사회성 좋고 뭐 그런 사람들이요 ㅇㅇ... 하나만 뛰어나면...
-
https://colormytree.me/2024/01GM2VCGWWJA2V92WE2...
-
설전정 중약 2
.
-
보통 어디부터 컨섩팅 거의 안 끼죠?
-
첫 정답자 1200덕 드리겠습니다!
-
군수생 달린다 5
크리스마스에도 연ㄷㅡㅇ 달린다
-
올해도 입금 감사합니다
-
둘 다 뽑는 인원수도 비슷하고 등수도 1등,2등임 최종컷보다 점수 높은건 1번인데...
-
ㅈㄴ 취함 9
엄빠랑 주향테스트했어요 근육이 수축/이완만 알아듣소 얼마나 작동할지는 알아듣지...
-
봇이지 뭐
-
그립습니다...GOAT...
-
서강대식 505 4
인문자전 발뻗잠 ㄱㄴ?
-
이정도면 괜찮나요??
-
국어하면서 느끼는건 이해에 몇시간 때려박아도 의미없다인듯 15
읽기 전략을 확실히 세우고 거기에 내 생각을 끼워 맞추는게 훨씬 나았음 몇시간...
-
디저트 추천좀
-
인생 0
쓰다
-
어떰????
-
진학사로 보았을때 경희대 글로벌 커뮤니케이션 학과가 6칸뜨고 건국대 건축이 3칸인데...
-
김범준쌤 평이 좋길래 수1수2 스블부터 들으려고햇는데 좀 버거워서 다른강사분...
-
고대기원24일차 10
꾸 준 글
-
영어도 좆돼고 한국사도 좆돼고 내신 일본어는 9등급이면 어디 가야함?
-
대부분 전자고르네 유튜브에서
-
저는 07 현역이고 정시로 공대만 생각중입니다(기계공) 제가 입시를 잘 몰라서...
-
솔크 벗어나고싶다ㅠㅠ
-
기만좀할게요 4
여친이랑 여친 친구들이랑 스시랑 와인임..
-
https://colormytree.me/2024/01JFMET4Y126MG3P6QY...
-
송민호는 왜 장기대기면제 안된거냐? 난 부실근무가 아니라 아예근무안하고 면제됐는데 개불쌍하네
-
6모 전까지로 기간 잡아도 될까요? 수학 공부 비중 높은 와중에 국어 분석할게 너무...
-
과연 진짜일까? 흐헤헤
-
같이 해주세요..
-
아빠 친구랑 생일파티는 어떻게했어?
-
어그로인거 아시죠?
-
니게tv 2달째 하루도 빼 놓지 않고 조이는 나!
-
행주치마는 행주대첩과 ㅈ도 상관이 없다 참고로 치마는 고려시대 혹은 후삼국시대에는...
-
약속있는 인싸인척 해야겠다
-
기하런? 1
2023 확통으로 1컷(15,22,29틀) 받았었는데 ㅈ같은 확통 못하겠어서...
-
하는거 너무 싫음 남자는 최소한 자기객관화는 한다
-
반드시 기숙사 구해야하나
-
시발점 대수 미적분1 각각 가격만 34000원, 36000원이여서 너무 비싸고 좀...
-
전 작년에 667 했는데 6칸 성대 떨어졌습니다
-
올해는 내가 더 행복해 커플녀석들아
-
좀 무서운데 이거는
-
https://colormytree.me/2024/01GM2VCGWWJA2V92WE2...
ㄷㄷ