크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
-
ㅇㅈ 6
오늘 받은 현우진 머그컵
-
조용히 좋아요 눌러볼까?
-
그 상태에서 살도 찜
-
나도 인증하고 싶어.. 17
하아..
-
인싸 나가 8
-
왜 아무렇지아는데 남자는 이상할까
-
수학 백분위가 96이거나 동라인대 인문계를 충분히 붙을 수 있는 성적인데 예체능...
-
배고파 배고파 배고파 배고파 배고파
-
수시광탈해서 정시로가야는데 54346이 진학사 쓰는건 돈 아깝나요? 8
그냥 지잡대 성적이니가 진학사 11만원결제해서 쓰는거 걍 돈낭비일가요? 그래도 쓰는게 나을가요 ㅜㅜ
-
안녕히 개새여 13
-
제가오늘 알바하는데 메뉴하나를 실수로 누락해서 포장을했거든요,,매니저님이 계속...
-
83.38인데 국숭 가능한가요?
-
진짜 세상이 날 속이고 있는 게 분명해
-
테.무 금지어 돼서 테-무 이지랄로 쓰노 ㅋㅋㅋㅋ
-
볼 때마다 기분 잡침
-
저는 친구없는데 어떻게 만드셨나요...
-
지금 이렇게 3개 쓰려고했는데 다군이 학교가 워낙없어서 찾다보니까 이게 나왔음 나는...
-
ㅇㅈ해주세요 2
-
초등학교때 이미 같이 학교다닌 전적이 있기 때문에 대학교도 같이 다님 된다 ㅇㅇ
-
동덕약대 고민 6
동덕약이랑 지방약 (강원, 제주, 우석, 원강 등등) 이면 동덕약대가 인서울이니 나을까요..?
-
ㄹㅇ
-
왜?????함????? 그 얼굴로?????????
-
딱 하루행복하고 끝임.
-
ㅇㅈ 6
제 담요예요 푸근행 ㅎㅎ
-
ㅇㅈ 17
오늘 여친이 찍어줌
-
하아....
-
재수해서 4
현역 때 강원대 낮은 과 광탈 ------> 재수해서 세종대 안정 ㅍㅌㅊ??
-
아무거나 물어보셔요들
-
음..
-
한발 늦게 생각하기에 후회로 남아 과거에 갇힌 사람 4
에피메테우스 내 닉임...
-
ㄹㅇ
-
밖에너무추워요 좋은장소추천좀해주세요 술집과친구집은못거요
-
믿을만한 정보 맞음?
-
ㅇㅈ(ㅂㄱㄸㅂㄱ주의) 14
-
에리카 공대, 인하대 상경, 광운대 상경 다 안정떠서 고민이네요 안정카드를 이...
-
안뇽하데여 13
-
너를 그리워하다 일 년이 가버렸어~
-
순서를 어떻게 부르죠?? 미기확 미확기 이런 느낌으로요
-
뱃지언제나옴 2
23일에 보냈는데
-
어느 날이 대한민국 숙박업소가 더 흥할까요
-
끈끈해져야함 인싸들 다 여자랑 놀러나가고 우리같은 진성 옯붕이들만 남아서 오르비를...
-
ㅇㅈㅎㅈㅅㅇ 0
-
이걸왜클릭
-
나 전 술마셔도 채팅이나 글쓸때 티가 안나요 맞춤법도 되게 잘지키고 틀리면...
-
전자담배도 담배인데 전자여친도 여친이다…
-
5년 주기설에 의하면 2025년 새로운 놈이 등장할 시기가 벌써 옴 ㅇㅇ
-
앞으로 당당하게 술 산다
-
심지어 다음주면 성인된지 3년차네
-
ㅇㅈ 5
이틀 전 출근룩
고능아ㄷㄷ