크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
와 시발 2시야 2
슬슬 잘 시간인가
-
도태한남백수말고 하와와 여중생이 되고싶어
-
서로 다른 노래 2개 틀어놧엇넹
-
자야겠다 8
슬슬 졸리네
-
ㅇㅈ은 1
너무 쫄려…. 넘 많이 올렷어 …….
-
ㅇㅈ메타 굴려줘 2
심심해요
-
입학처 홈페이지에서 다운 받으라는디 작년꺼밖에 없는데 어디있나요?
-
ㅇㅈ 26
은 새벽에 해야해요
-
고대 문과컷 1
작년 최종 70컷보다 점수 낮은데 낙지 6~8칸 뜨는거 정상인가요?
-
오늘부터 국숭세동이다 ㅉ
-
메리 크리스마스 1
정시님들 곧 원서 쓸 시간이 다가오는데 다들 꼭 원하는 대학/학과 붙으시길...
-
[단독]연세대, '시험무효' 소 취하 동의…'논술 유출' 법정 다툼 마무리 14
[서울=뉴시스]임철휘 기자 = 연세대 2025학년도 수시모집 자연계열 논술시험을...
-
오르비 재밌다 1
내년에도 하면 안 되는데... 관성이다 ㄹㅇ
-
난 자러감
-
공부 2
고오오오옹부
-
의대 목표로 공부하려고 합니다 원래는 문과였는데 어떤 이유때문에 다시 공부를...
-
잼민이 시절•• 5
-
애니프사 키메타,ㅇㅈ메타 열지 않기 키,얼굴,연애로 ㄱㅁ하지 않기 ->이거만 지켜도 호감된다 ㄹㅇ
-
고속 텔그만 보고 쓰시는 분들 없나요?
-
너무 존잘 기만러들이 많아서 못하겟다
-
아오그냥개빡도네 2
내일 커플들 손잡고 즐거울거 생각하니 개빡돔
-
도와주세욧 0
탐구1 94 탐구2 87
-
전 잡니다 9
ByE
-
이 정도면 뻔하지 않다고 생각함
-
느그들 인스타로 가서 놀아라
-
야밤이네요 4
Kfc네요
-
실제로 본인 얼굴 사진을 올리는 사람이 있나요?? 한 번도 못봄
-
화학 10점이면 0
백분위 8이네 ㅎㅎ
-
걍 잘래 2
푹자고 단다단 정주행 강연금 만화 2회독 노래듣기 하면서 옯붕이들이랑 놀래 낼 활동...
-
옛날 사진을 알아봐야하는데 셀카 같은걸 안찍는단 말이에요 쓸 사진이 없네
-
2월말 기숙재종 들어가기전에 이원준 인강을 잠깐 듣고 갈려는데 독서 goat인가요?...
-
남녀비율 5
오르비는 남녀비율이 어느정도 될까오?
-
f(x) ㅋㅋㅋㅋㅋㅋ
-
하아,,외로워요
-
항상 댓글 달러 갓는데 10
나보다 빠른 댓글이 하나 달렷다?한 명밖에 없음
-
ㅇㅈ 6
오늘 받은 현우진 머그컵
-
에휴 메타인지가 부족하구나 스터디코드 재생목록 2회독하고오세요
-
걔네 보고 어? 나쁘지않은데? 하고 생각한적 있음... 나도 그정도 레벨인것같아서
-
기만이 분명하군
-
조용히 좋아요 눌러볼까?
-
그 상태에서 살도 찜
-
나도 인증하고 싶어.. 17
하아..
-
인싸 나가 8
-
왜 아무렇지아는데 남자는 이상할까
-
수학 백분위가 96이거나 동라인대 인문계를 충분히 붙을 수 있는 성적인데 예체능...
-
ㅇㅈ 9
-
메모나 저장 안해놓으면 까먹는데귀찮아서 안하고 까먹음 병신
-
배고파 배고파 배고파 배고파 배고파
ㄷㄷ