크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
연례행사아니냐 저건
-
큰 일은 우리 팀 1/8/2 정글같은데
-
갓원영 미모가 절대 실존인물일리 없다 이말이야
-
누구일까
-
-
그냥 저사람 떡밥 굴려서 오르비에 남은 고닉 찾으려는거네 1
대 다크히어로 대 대 대 ㅋㅋ
-
1.애니프사 2.버튜버프사 3.아이돌프사 4.연에인프사 5.노프사
-
매국노라 공부해야됨. 이다지랑 권용기중에 들으면 됨?
-
쵸 카와이
-
뭔일임 3
진학사 표본분석하고오니까 난리났네
-
1. 테-무에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
에휴다노 7
에휴다노
-
크럭스 컨설팅 신청했는데 그럼 지금 시기에도 막 분석중인거임 ? 0
언제부터 분석을 하는거지 흠
-
뭐 물어보면 다 문제래 라고 하면 안 되겠죠?
-
사진은 봐주세요 3
이건 입체라고요!!!!
-
정시에 집중해서 쭉 공부하다가 논술 준비해도 될까요? 연대 논술 준비하고 싶은데...
-
찍혀서 며칠뒤엔 오르비못함..
-
비식 보면은 토했을 듯 ㅋㅋㅋㅋ
-
-
왜 클릭
-
흠.
-
제목보고화들짝놀라서 들어온애니프사면7ㅐ추
-
지금으로썬 게이픽인데 원서접수 당일날 롤코탈까봐 쫄림;
-
문서등록하면 2월달에 등록금 내기 전까지 아무것도 안해도 되는거겠죠…? 자꾸 불안하네요
-
진짜 개재미없음 저거하라면 과탐할거같음
-
모의지원 기준 건양 52퍼인데 이게 되겠냐고... 왜 자꾸 희망고문 시도하지
-
제가 쓸곳 아직도 안찼는데 의대 정시 표본이 크리스마스 끝나고 많이 들어올까요? 진학사
-
전 impulsive
-
걍 찐따인게 1
어떻게 해야 관심 받을지 젤 적이 많을 내용 눈에 불을 키고 하루종일 찾고...
-
-
여기는 몇 년 동안 그런 ㅈ목질로 굴러간 커뮤임. 이걸 못 버티겠으면 오르비를 안...
-
ㅇㅈ 2
예쁘죠
-
25올오카 듣는 중입니다 오답 복습할 때 왜 이 선지를 골랐는지 생각하고 정답은 왜...
-
무려 3집 가수임
-
이녀석들 쓴맛좀보자
-
몇퍼정도됨??
-
그거 규제하려면 사이트 관리자가 개빡세게 일해야 할텐데
-
저격인가 0
가끔은 맞는 것도 괜찮죠 홀홀
-
현생에서 직접 만난 사람도 아니고 커뮤에서 남 눈치를 왜 봄 ㅋㅋㅋㅋㅋ
-
생각해보니 수만휘가 은근 빡세게 관리할텐데 포는 약간은 널널하고
-
-
잠 피시방 잠 피시방 잠 피시방 오늘도 아침까지 달려야겟다
-
사탐vs과탐 2
국수영에 몰빵해야하는데 25수능 과탐 둘다 1등급이면 사탐 새로 배우는거보다 과탐유지가 낫나요?
-
라고할뻔~
-
1. 테-무에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
그럴거라 믿습니다
-
그동안 수학공부하면서 문제풀이 위주로 수학에 대한 이해도가 좀 낮았던 것 같은데...
-
그 사람은 오르비랑 안맞는 거 아닐까... 여기 비율 걍 애니프사5 노프사3...
-
-
거기는 좆목질 없이 찐 재밌는 커뮤긴함 성향에 따라 시대갤이 더 맞는 커뮤인 사람도 훨씬 많을듯
고능아ㄷㄷ