크리스마스 트리 꾸미기
게시글 주소: https://9.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
-
구글에 박제되나
-
문과 표본이 너무 안 찬 것 같은데 추합 끝나면 우수수 들어올까요?
-
인과계랑 싸웠나 너땜에 가군을 못지르잖아
-
안녕하세요 12
술좀마셨어요 행복버튼ON
-
지금 밖에 사람 많을거라고 내일 하자 하시네 오늘은 걍 돈까스 시킴
-
전화 추합 3
한양대 융전 예비 앞번호 떠서 낼이나 모레 전화 추합 될 것같은데.. 이미 고대...
-
크리스마스인데 연말 분위기나 내자
-
ㅈㄱㄴ
-
ㅇㅈ 3
이건 제 풀떼기 하루종일 집에만 있기 내일도 그럴 예정임••
-
정시로만 대학가려는사람중 영어 1비율이 작년보다 그렇게 많진않다 가 정배인가요?
-
서성한 정도 대학인데 한 70%정도 들어왔을까요?
-
폰배경ㅇㅈ 4
.
-
공대 어느정도 갈 성적이에여?? 경희대 시립대 정도인가요?
-
“40년전 무임승차 이제야 갚아요” 부산역에 200만원 놓고 사라진 여성 0
40년 전 기차에 무임승차한 여성이 부산역에 200만 원을 놓고 사라졌다. 24일...
-
자연계열 어디까지 가능? 기공, 물리 생각중
-
전남의대 05학번 가정의학과분은 언제 가실련지..
-
맛없어요!! 마트에서 가성비샴페인사서 그런가
-
ㅇㅇ
-
왜조용함? 4
다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어...
-
"정시"로 대학 못갔으니까 "늦게" 가면 되는데 ㅋㅋㅋㅋㅋㅋ
-
ㅇㅇ... 클쓰 후로 최종컷에 수렴함?...?
-
는 어그로구요 학고반수해서 다른 곳으로 옮길 예정인데 학고반수 하기 전 오티만...
-
내가 걔보다 못한게 뭔데... 시발진짜뭔데내가 어? 어? 어? 응?
-
7시되니까 딱 지옥철 풀리노 강남역지나와서 그런가
-
98 92 2 79 99가성대경영5칸인데 92 90 2 92...
-
너무 오바인가
-
으흐흐..
-
삼육약이 전통이 있다고 들었는데 어디가 괜찮을까요??
-
하시발 9
유니야 나 좀 믿어봐도 되겠니
-
458 ㅁㅌㅊ 4
-
진짜 예능,방송,음악활동,기타 활동 여러가지 등등 다 참여해서 다른 부문으로 인기를...
-
솔직히 경쟁사 하나만 있어도 서비스 2배는 좋아질듯..
-
테레비에서 하고 있는데 볼 만해
-
학창시절 내신에 손놓고 정시공부해서 내신은5~8등급 모고수능은1~2등급인데 서울대는...
-
광운대 건축, 세종대 공과계열, 전남대 기계 다 기숙사 살아야 합니다 님들은...
-
몇 명 더 들어오면 칸수 훅 떨어지고 나가면 훅 올라가고
-
변표 뜨고 6칸 초반에서 5칸 초반 됐는데 불안하다 너무
-
유대종, 강윤구 풀커리 타고 26 수능 도전해봅니당 3
약 N년 전에 현역으로 대학 갔던 아저씨입니다. (그래도 2000년대임...)...
-
보통 이런곳에서 빵나나요? 아니면 마지막날쯤 우수수 들어오나요?
-
30명 넘게 뽑아서 불확실성은 좀 덜한 대신 3칸에서 5칸으로 갑자기 오른 게 계속...
-
좀 ㅍ해주세오ㅠㅠ
-
감사합니다 한양대 ㅠㅠ
-
정시 라인 0
언미영생1지1 93/92/2/87/91 수시 다 떨구면 진학사 사려해서 라인 같은...
-
표본분석 시작 0
표본분석 시작하려고하는데 표본분석이 앞 등수 애들이 실제로 어디갈지 보는...
-
낙지 설대컷 조금씩 내려가네요 더 빨리 내려가라~~
-
기만자들
-
으흐흐..
-
인하대 대형과 진학사 서비스 시작부터 6칸 최초합~추합 왔다갔다 하는데 안심해도...
ㄷㄷ