크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
관심이 없어보인다..접자
-
어디가 더 높나요?? 인식이 궁금함 ㄹㅇ 몰라서…
-
아이유vs박보영 0
누가 더 이쁨?
-
재수해도 될까요 0
정말정말 부끄럽지만 고3내내 정신건강 이슈로 하루에 한시간도 제대로 공부를 안 했고...
-
내가 꼭 올해 0
의대 가서 혈육 짓밟아준다….. 3년동안 시대에 갖다 바친 의미없는 몇 천을 생각...
-
진읽남일거 같긴한데 ㅋㅋㅋ... 가려니까 또 아닌거같고...
-
아오
-
고대 랜덤채팅에서 만난 어떤 사람이랑 지인한테는 털렸어요
-
이럼 안되는데
-
본인이시면 쪽지 부탁드려요 일단 애니프사에요
-
많은 듯….. 그래서 계속 입결이 엎치락뒤치락 하네요 눈치게임 ㄹㅇ… 약폭 약빵...
-
닉변을해보았다 0
-
실명 털린 적은 없지만 12
오르비언에게 사는 곳 특정당하고 미친척하고 전번을 스스로 깐적은 있어요
-
그럴 수야 있어
-
사실안까인게없어
-
흠...
-
나도 고3 때 연대 고대 응원가 ㅈㄴ 보면서 나도 언젠가는!! 이 대학에!!...
-
의대면접자료제작하고있습니다 게시글읽고 연락주세요
-
학과중에서 가장 6
뭐랄까 그분야를 진심으로 광적으로 오랜시간 좋아하는 사람이 적은 학과가 어디일까요?...
-
반갑다 게이들아 10
-
이번 수능 인천대 세무학과정도 갈수있는데 재수해서 인서울은 해야할까요?
-
연대 폭 0
실지원은 아니라서 모르는데 전체 등수 360명 중에 47등이면 폭발 감안하고...
-
학폭PTSD땜에 사람이랑 편하게 대화하는게 어려워요 노력하고 있는데 힘드네요
-
실모풀기좋은자리가있데 좋아좋아
-
1차 떨군것도 열받는데 이것도 언제까지 미룰래 ㅅㅂ
-
ㅤ 2
22수능 화작/미적/화학1/생명과학1 96/98/2/78/84 23수능...
-
내년 연대 내신반영 50만점에 47.5인데 연의 가능? 1
얼추 계산 때렸더니 47.5 나오네요. 수능은 자신있는데 내년에 또 내신반영해서.....
-
이 움짤이 진짜 ㄹㅈㄷ
-
제발 붙여줘.. 총 모의지원자수는 그대론데 등수는 계속 밀리는구나...
-
ㄹㅇㅋㅋ
-
생물 예습..? 4
수능 물지봐서 메디컬 가면 생물학 따라가기가 힘들까요..? 화학은 자신 있는데...
-
우리 부모님은 좋은분들인데 왜 나는…
-
쿨쿨띠 8시부터 4시까지하고 공부 좀 하다가 저녁 먹고 지금 샤워 마침
-
싫어서 출산도 못할듯
-
삶은 무엇일까 21
삶은 계란 우하하
-
내신 7등급 장수생 세특 안챙김 맘편히 8칸 쓰러감
-
의류학과 넣을 건데 권장과목에 화1생1 있더라고요 전과목 2.1 주요과목 1.9인데...
-
전설의 22수능이후로컷이 48 48 47인데 교수님들 존심상할때도됏다
-
예1까진 과외를 한다고 쳐도 그 뒤론 공부만 해야할 것 같은데 집에서 5년동안 용돈...
-
휴학 반수 할라하는데 어머니가 1~2월에 학원 보내려고 하시는데 대구 러셀 가지싶음...
-
표본분석하는데 0
진짜 너무 짜증난다
-
너무 쫄려요 진학사 5칸 추합 텔그 모의 54 / 자체 57 고속 연초 메가 최종컷...
-
민심CHECK
-
100명 가까이 받지 않나..
-
다들 낙지 들어오셨나요? 표본이 너무 안 차는데.. 이러다 폭발할까 걱정입니다.
-
연세대 의대 가능? 언미물지 나는 아니고 친구가.. 수학 96
ㄷㄷ