크리스마스 트리 꾸미기
게시글 주소: https://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 (+2,500)
-
1,000
-
1,000
-
500
-
-
실모 비싸
-
아자아자 ㅎㅇㅌ!!
-
미소녀 여고생임 4
ㅋㅋ
-
어그로 죄송합니다 90 96 2 96 96(사탐) 이면 서강대 전자 가능한가요??
-
쉽지 않네,,,
-
수제버거 체인점인데 햄버거 너무 맛있었음요 가격은 근데 비싸더라구요
-
노숙하러 서울역 가는중
-
사문이나 경제 기준이면 더 좋고
-
할수이따 0
불(꽃)가능
-
문제 개념편 인강도 듣는게 좋아요? 걍 오답하고 틀린거만 보는거랑 큰 차이가 있나요
-
미소녀로태어날걸 11
로그아웃!! 리셋
-
현역 국어 5등급 재수생입니다. 강기본 듣고 강기분 독서, 문학 거의 끝나가는...
-
현역 학교에서 공시 3-4시간 뽑아내면 괜찮은건가요.. 5
수시 완전 버린 건 아니라 들어야하는 수업이 좀 있어서요ㅠㅠ
-
오늘도 내 저녁은
-
안녕하세요! 오랫만에 돌아온 bennet foddy입니다 이번시간엔 수학이라는...
-
첫 정답자 5000덕 드리겠습니다! 암산으로 풀어보아요 풀 수 있으면 :)
-
맛저하셔유 3
뿌링클 맛있겠죠
-
본인에겐 모든 과목이 타임어택이라 조언을 듣고싶어용
-
밤일했더니 낮에 에너지가 없음
-
건강의 중요성... 10
건강이슈로 채플 쨌습니다...입학 이래 최초의 자체휴강 더군다나 흐린 날만 되면...
-
확통 3초반 정도 실력인 것 같습니다 이해원이랑 n티켓 중에 고민 중이에요 강의보단...
-
투표해줘 0
100덕코씩 10분 드릴게요 [보유한 신발] 반스 어센틱 레드 컨버스 척 70 로우...
-
이게 얼마야
-
미마정 수학 ㅈㄴ 못할거 같네 닉네임
-
오늘부터 이걸로 간다
-
나는 어떡하죠 2
아직 서툰데
-
나무위키에서 배기범 강사 글 보니 사법시험도 잠시 준비했었다고 나오네요. 1
1년 정도 준비했다는 것을 보면 1차 합격까지는 못 간 것 같은데... 오히려...
-
못참겠네 2
나도 내가 밉다...
-
수학문제 풀어주실분 20
인스타에서 본건데 못풀겠음 풀어줘요 실근갯수7개
-
20회 4시간컷인데 계산 빡빡한거 몇개 있어서 생각보다 오래걸림 ......우흥
-
장난감 시계네 아기자기한
-
-
무지성n제 30번 19
맛들린 사람
-
윤씨 방청신청함 10
근데 이거 방청신청 뽑히면 나 티비에 나오는거임? 이건 좀 그렇군ㅋㅋ
-
게이되긴했음요 진짜 멋있긴하더라..
-
낭만부럽다나도할래..
-
요새 정시 어렵냐 11
18수능 23111 인데 수학 실력올리면 지방대 약대 가능?ㅋㅋ.. .
-
로켓대학교 의예과 로의
-
간쓸개 오답방법 0
작년 간쓸개 파이널 사서 풀고있는데 틀린문제 있으면 지문 뜯어보면서 오답 꼼꼼히...
-
국어 공부법 1
제가 국어 인강 안보고 하다가 재수하면서 강기분 수강 중인데 공부 방법 이게 맞는지...
-
손이 빠르면 머리가 고생을 안한다
-
동네 스카 다니는데 여기 사람이 별로 없음 그리고 룸이 3개임 (a,b,c,) 난...
-
오늘 만우절이람서요 25
오늘은 어떤 구라를 쳐볼까 안녕하세요 X6년생이에요~
-
기세 마치 폭포 실패는 no more victory or nope~
-
고대과잠 7
안입는데 버릴까
-
월 일
-
무슨의미지 키가 커서 닮았다는건지 잘생겨서 얼굴이 닮았다는 건지 모르겠다
-
오늘 뭔 날인가
-
하쿠 하울을 기대하면서 사진 넣어봤더니 벼랑위에포뇨 남자 애기가 나옴 ㅅㅂ
고능아ㄷㄷ