크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
새벽2시인데 배고픔뇨
-
탈릅함 15
굿바이
-
고양이 ㅇㅈ 1
엠티갔을 때 친해졌어요
-
ㄴ[ㅔ
-
민지야 4
-
김승리쌤 커리중에서 강민철쌤 강기분처럼 기출 분석 강의 있음? 커리만 봐서는 잘 모르겠던데
-
하 ㅈ도 모르겠네 걍 ㅋㅋㅋ 뭔가 이번에 대학들 다 추합 많이 돌것 같은 느낌이...
-
너무감동이고... 너무감사하고... 그냥너무좋았음 힘들때마다 꺼내볼께요
-
이 노래를 듣고 중고등학생 시절이 떠올랐다 <-- 틀딱 2
난 초딩 때가 떠오르므로 난 젊은이
-
하시모토아리나 0
왜들어옴?
-
너무 부럽다
-
그것도 1학기 이후론 뭔 엽사밖에이 없네요
-
메리 크리스마스 5
HAPPY 2026
-
보시는 바와 같습니다. 아주 기만러들 밭이야
-
예쁜 미쿠 보고 가셈요 16
-
초딩때 한입했다가 죽을뻔해서 직접 사서 먹어본적이없는... 요즘엔 계란 올려가지고...
-
술로 보내는구나 어휴...
-
오레오 먹는중 1
하나 드세요
-
말씀드리기에 앞서 현재 제 위치를 말씀드리자면, 25 수능에서 마킹실수로 3점을...
-
테-무 2
-
ㅇㅈ 5
야무~~~~~디게 먹어야디~~~~~~~~~~~
-
정시 지원 할 때 필요한 서류에 고등학교장 직인을 받아야 하는데 3개 이상 받아도...
-
제가 심각한 수학 노베라 지금 동네 노베 가르쳐주는 학원 다니고있구요 나머지는 제가...
-
여기 사람들 너무 착함 15
ㅇㅈ 하면 다 예쁘고 잘생겻다고 해줌 따뜻한 사람들…..
-
예나 3
-
ㅇㅈ 5
ㅌㅋㅋ
-
나랑 애니볼래? 8
-
오노추 2
ㅠㅠㅠㅠㅠㅠㅠㅠㅠ
-
아니 애니 프사는 맞잖아요
-
저는 롤체하러감 1
-
ㅇㅈ햇으니 이제 잔다 30
응..
-
외롭다 시발 3
…
-
ㅋ
-
와 시발 2시야 2
슬슬 잘 시간인가
-
도태한남백수말고 하와와 여중생이 되고싶어
-
서로 다른 노래 2개 틀어놧엇넹
-
자야겠다 8
슬슬 졸리네
-
ㅇㅈ은 1
너무 쫄려…. 넘 많이 올렷어 …….
-
ㅇㅈ메타 굴려줘 2
심심해요
-
입학처 홈페이지에서 다운 받으라는디 작년꺼밖에 없는데 어디있나요?
-
ㅇㅈ 26
은 새벽에 해야해요
-
고대 문과컷 1
작년 최종 70컷보다 점수 낮은데 낙지 6~8칸 뜨는거 정상인가요?
-
오늘부터 국숭세동이다 ㅉ
-
메리 크리스마스 1
정시님들 곧 원서 쓸 시간이 다가오는데 다들 꼭 원하는 대학/학과 붙으시길...
-
[단독]연세대, '시험무효' 소 취하 동의…'논술 유출' 법정 다툼 마무리 14
[서울=뉴시스]임철휘 기자 = 연세대 2025학년도 수시모집 자연계열 논술시험을...
-
오르비 재밌다 1
내년에도 하면 안 되는데... 관성이다 ㄹㅇ
-
난 자러감
-
공부 2
고오오오옹부
-
의대 목표로 공부하려고 합니다 원래는 문과였는데 어떤 이유때문에 다시 공부를...
ㄷㄷ