크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
이건아직 모르겧음..
-
멍
-
는 개인적으로 없다고 생각하는데 오히려 올바른 방법으로 공부해서 좋은 성적을...
-
나 없던 사이에 글댓을 몇개나 쓴거야
-
근데 확실히 감성이 많이 다르네 BL 느낌도 ㅈㄴ 나고 86가 ㅈㄴ 독특한듯
-
다자녀면 공군 0
얼마나 유리한가요? 영향이 어느정도인지 궁금합니다
-
교수님 안 주무세요?? 기습 계엄도 아니고 새벽 발표라뇨
-
선제리 아낙네들 2
먹밤중 한밤중 새터 중뜸 개들이 시끌짝하게 짖어댄다. 이 개 짖으니 저 개도 짖어...
-
군대갔다왔다고는 해도 03이면 내년수능보기는 너무 늦었겠지 그래도
-
크리스마스에 할짓없어서 옯비 보다보니까 ㅅㅂ 삼수생각 ㅈㄴ드네.......하아
-
자야지 4
-
좀 최신 애니인 사펑 엣지러너를 봤으니 암굴왕 같은 명작 틀딱 애니나 볼까
-
반수의 결과로 가치 있을까요? 중대가 더 높아졌긴해도 사회나가면 중경외시...
-
잘자요 4
다들메리크리스마스
-
병약미소녀 ㅇㅈ 23
은 구라고 그냥 ㅂㅅ임 펑
-
모두 잘자요 9
다들 행복한 이브 보내셨나요? 전 아싸라 늘 지내듯 지낸 것 같네요.. 모두 잘자고...
-
한국정발하면저걸로바꿔야지
-
현역인데 여기 못가면 재수할 예정인데 합격확률 0퍼센트인가요? 7
ㅜㅜ..그리구 이해가 안가는게 최초정시 모집인원이 238명인데 저기 등수 안에잇는데 3칸 ㅜㅜ
-
-
산타랠리 에 숏을 쳐?
-
하루종일 오르비를 지킨 자의 훈장
-
에 전혀 관심 없는 건 아닌데 n이 늘어나니까, 연애 감정이 무뎌져요.. 연애...
-
기만글만 안쓰면 욕 안먹을 텐데
-
ㅂㅂ
-
안돼 가지마!!!
-
크리스마스에 여친없는 애들끼리 놀고있으니까 ㅈ같음이 2배 흐흐
-
저능부엉이
-
이제 자야돼 2
내일 또 보자 옯붕이들
-
zzz 2
-
(고려대)의대 면접 보는데 얼마 정도 시간이 소요 되나요?? 고려대 아니어도 한번씩만 답변좀...
-
ㅂㅂ
-
1. 테-무에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
이제야깨달아버렸다
-
글 안 올라오네 2
임마들 다 어디감?
-
감성이 다르노 결말이 너무 성급했단 느낌은 아무래도 이 애니가 10회라는 분량밖에...
-
논술 예비 받음 ㅋㅋ
-
-
정시의벽 <<< 6
이 사람도 글 쓰는 거 까먹어서 아까 호다닥 글 쓰고 또 한참 잠적했다가 나타남...
-
일본영화 추천좀 2
잔잔한거 좋아함 넷플에있는거로 ..
-
이렇게 푸는거 맞나요 재밌네요 ㅋㅋㅋ
-
표본이 제일 많은 진학사가 컷이 높아서 컷이 낮은 고속 텔그를 믿지 못함 ㅜㅜ
-
ㅋㅋ 동지들
-
여르비 ㅇㅈ해도 누가했는지 다까먹음 망할거 닉보고는 여르비인지 못맞출듯
-
막상 좋아하는 사람 보면 이상형과는 좀 거리가 있는 듯요
-
쌍사 이 씨발럼
-
자야지 6
잠뇨
-
???: 이거 정적분 정의 아님?? 이건 미적분의 기본정리라고!!!!!!!!!!
-
컴이나 정보대학
-
저 하나 질문좀요.. 지방사는 사람들이 서울권대학으로 가려는 이유가 뭘가요? 8
단순히 대학 네임드때문일가요? 제가 공대가 목표이고 전북에서 사는데요..어차피...
-
이상형 말해주새요 저는 저보다 키크고 귀여운 사람!
고능아ㄷㄷ