크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
탈릅하시고 어딘가에 잘 계시겠지 했는데 그렇구만 반갑습니다
-
부정선거 의혹 검증 완료. 게임오바.
-
자존감낮으면 0
군대가보면됨 세상저런ㅂㅅ들이없음 내가 정말착하고좋은사람임을깨닫게됨 자존감쑥쑥
-
저 종사(從社) 세력 말을 믿지 마시고 과탐에 전념하시길 바랍니다.
-
진주보다 더 고운 아침 이슬처럼
-
예쁜말 고마워요 ㅎㅎ
-
나 뉴르비다 4
안속는다
-
시간 날 때 꼭 보세요
-
진짜 사랑해요 다들 31
트리써준내용보고 진짜울었어요 사랑해요다들 너무고마워요...
-
신음 써주신 분도 고마워요 헤읏..
-
솔크다ㅏ
-
ㅇㄴ 0
영국에서 온 편지 쓴 옯비언 자수해라ㅋㅋㅋㅋ 진짜 길어서 기대했는데 비겁하게 피지컬로 웃기네
-
기분이 좋아졌어요
-
나는 말 이쁘고 화려하게 포장하는건 재능없나봐 받은것들 말 넘 이쁘자나…
-
사랑해요
-
제 트리는 7
내년에써주세요 군대가기직전이겠네요
-
커뮤의 순기능
-
초성만 있어서 모르겠어
-
이렇게된거 인터넷친구들과 함께할까
-
기분이가 좋다
-
재수생입니다. 백분위가 가장 꾸준히 잘 나오는 위 세 과목 중 한 과목 고르려...
-
나 왔다 5
^ 21년차 모솔아다 ^
-
나보다 어린 누군가가 무언가를 잘하는 걸 봄 -> 나는 쟤보다 나이도 더 먹어놓고...
-
9월에 가산점 정상화 이후론 높아봐야 92~93일듯
-
후후훟후후후후후후 하하하핳하하하하하하 아이민... 확인... 완료.. 으헤헤헤헿헤 하하핳하하하
-
강기분 들으려다가 OT에서 3인가 4이하면 강기본부터 들으라하는데 강기본 우선인게 좋겠죠?
-
트리야 아프지마 2
서버가 아파해요 서버 건강 절대 지켜
-
작년 6모에 2, 9모에 1, 수능에 2였고 그 외에 모든 학평은 1등급이었습니다....
-
무한로딩이야
-
조유리즈 3
니게tv 개국 62일차
-
재밌는 글들이었을 거 같은데 흠뇨이
-
하지만 인스타에 올려도 친구들이 어차피 안 써줬을 거니까 신 포도겠지...?
-
나 울게 하지마라.. 안 운지 2년 됐다고
-
나도 트리할걸 2
괜히 뺐네 다들 신나하는거 보기 좋네요
-
힘드네 3
후
-
언매는 전형태 올인원 선택했습니다. 작년에 화작 백분위 76이었습니다....
-
미필 04 사탐런 반수 어떻게 생각하시나요..
-
전 필력이 딸려서 길게 못쓰는 병이 있어서 길어도 5줄이 최대라 ㅈㅅㅎㄴㄷㅈㅅㅎㄴㄷ
-
아니 뭐지
-
-
지가 여르비래
-
내 트리를 내가 못 보는게 말이 되냐
-
메리크리스마스 4
-
한석원t 1
한석원t 4규 들을까 고민이라 먼저 커리or한번 보려했는데 원래 한석원t는 오티...
-
트리가안열려 3
망햇따리
-
어느대학공대랑 비슷하게할까요
-
어떻게 처음부터 이거 6연타야
-
이 목표임뇨
-
아랫집 미쳤네 5
크리스마스면 방을 잡고 하라고.. 왜 자취방에서 하는데
-
성적표 받자마자 SIUUU 외치면 CR7, 신두형의 은총을 받아서 77777에서...
고능아ㄷㄷ