크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
이번 수능국어 4등급 나왔습니다. ㅠㅠ 현재 고려중인건...
-
걍 취미로 하려는데 수능 강의가 도움이 될까요?
-
진학사 표본 분석할 때 예를 들어 진학사가 최초합으로 잡아놓은 인원들이 15명이라고...
-
저 왔어요 13
이해가 안 되는 게 16시간만에 왔는데 투데이가 왜 253이지...?...
-
어느 라인대인지 감도 안잡히네요 인가경은 많이 힘들어 보이나요?
-
여르비 ㅇㅈ) 9
-
기습투척 5
내여친임 옆에서 자려하길래 찍엇슴.. 용하형 실장해줘..
-
현재로서는 cpa 계획중입니다. 과만 생각한다면 닥전이긴한데 중앙대가 cpa...
-
떡각 4
?
-
낙지 설인문 갑자기 110명대로 줄어들엇는데 대체 왜지
-
왤케 조용해 2
자야겟다
-
가끔 보면 초록색으로 의라고 써져 있던데 오르비 처음이라서 잘 몰라요.. 누가 설명해주실분 ㅜㅜ
-
수능폐지해라ㅉㅉ
-
오늘은 진짜 조용하네
-
트리 5
https://colormytree.me/2024/01JFVW2Y9JBG34GDRR6...
-
크리스마스 노래 1
-
15분 남았으니 6
마지막 트리 써주세여~~~...
-
트리 ㅈㄴ 달리는중
-
얘들아 심심하다 5
질문좀 해봐
-
ㅅㅂ 4
올해는 솔크가 아닐 줄 알았지
-
와시발 카메라키니까 몰골이 말이아니네 걍 자러가야겟다
-
스킬 잘 가르쳐 주시나요? 다른거랑 시간 겹쳐서 못 들어서ㅠㅠ
-
다 깐건 처음이라 좀 부끄러운디
-
수능으로 하바드 정도는 가야 정상임ㅉㅉ
-
야식 추천좀 0
ㅈㄱㄴ
-
슬프네 1
내일 약속 있는 사람들도 많아 보이고
-
이거 등수랑(4/68) 모의지원 탭에서 보는 등수랑 다르던데 무슨 차이가 있는건가용
-
잠시 들려요 2
내일 저번주에 미리 만들어둔 연애모의고사 올릴게요 글구 저는 갑니다 ㅃㅃ 마지막인데...
-
아오 배신자 자식들
-
올해로 n수화장연지박생들 털고 표본정상화+불화학뜰듯 반수하게되면 내년도 화1으로간다ㅇㅇ
-
경희대 기계 0
경희대식 점수로 558.9점이면 붙을수 있을까요 지금 6칸이긴한데 지금 진학사는...
-
이건 Wham!이지
-
ㅠㅠ 문제되면 글삭함...
-
ㅇㅈ 9
하루종일 잠만 잤어요
-
ㅈㄱㄴ
-
https://link.yeolpumta.com/P3R5cGU9Z3JvdXBJbnZp...
-
강민철 현우진 2
둘이 같이 술마심ㄷㄷ
-
ㅇㅈ메타인가 2
크리스마스에 눈이즐겁겟군아
-
김에 밥을 올려 0
올려서 밥 우에 우니를 올려 올려서 김으로 밥과 우니를 감싸서 한입에 넣으면 맛있어요
-
ㅅㅅ
-
바로 실지원 26명에서 108명으로 늘어났네요 ㅋㅋㅋㅋ 원래 700점에서 690점...
-
나만 불행해
-
사탐발림에 넘어가지 마십시오!!!
-
동성친구도 없으면 어카나요?
-
다군 안정 카드로 외대 자전과 홍대 자전 중 어느 곳을 추천하나요? 진학사 기준...
-
님들 큰일남 2
제목 어그로 ㅈㅅ합니다 723이나 733으로 원서쓰는거 어캐 생각하니사용?
-
두고보자..
ㄷㄷ