크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
정말 좀 친다 하는 문과생들 cpa 준비 많이 해서 회계사가 그렇게 잘버나 싶네요
-
벌써 몇번째인지 모르겠노 접을때가 됐나
-
새터 날짜 2
새터 보통 날짜가 어떻게 되나요? 오티도 알려주세요!
-
눈 침침하고 물 많이마시고 발 저리고 밥 많이먹는데 혈당치는 찌를때마다 지극히...
-
口是禍之門 (구시화지문) 입은 화를 부르는 문이고 舌是斬身刀 (설시참신도) 혀는...
-
전자후자 뭐가더좋음?
-
궁금함
-
Was turn?
-
-
몽글몽글
-
ㄹㅇ 궁금한디 썰좀 풀어주세요
-
확통런 3
안녕하세요 올해 재수를 하는데 선택과목때문에 고민이 많습니다...2025학년도 수능...
-
차기 갤주 등장 2
대 요 요
-
자가진료는 좀 필요해보이긴 함
-
현역이 실모 시즌에만 바짝 해도 백분위 99가 나옴
-
이게 건축공학처럼 보여? 빼박 건축학과 아니야??? 자전 전공소개에 이렇게 돼있으면...
-
차단 꾸욱 9
-
근데 정신건강을 좀 챙겨야거같아요 선생님 의사샘이신거같은데 환자보기보다도 자신을 좀...
-
너무 즐거워서....다들 투투 해야겠지? (제발 해주세요)
-
작수 높4등급 나왔는데 문학은 3개 틀리고 비문학은 6개 정도 틀렸어용 나머진...
-
오스 보드따고 로컬 나간다 해서 오쓰 그 자체가 자기 전문이 되는게 아님 환자를...
-
홍대 기계 점공 7
붙을 수 있을 까요??
-
개정 많이 됬나요???
-
좋은걸까요 안좋은걸까요
-
아수라에서 올해 수능 이럴'수도' 있어 라고 한것중에 진짜 그렇게 된게 많긴한듯...
-
지금 수업구성이 어떻게 되나요?? 뭐하는지 알려주세요..
-
빵이었으면.. 고대 저처럼 점공률 40퍼 밑인분들 있을까요?
-
젊은 성인 2형 당뇨 증가세...고칼로리 식습관에 의한 비만 인구 증가가 원인 4
[이데일리 이순용 기자] 식습관, 생활습관 등의 변화로 만성질환이라 불리는...
-
재밋음
-
별 감정 안 생길 줄 알았는데 슬프네 내가 굉장히 많이 미워핬던 사람인데도
-
아가 기상 8
모두 안녕
-
물1 4만 5천명 화1 2만 5천명 생1 8만명 지1 12만명 물2 1만명 화2...
-
정수 범위 내에서 한정짓나요? 분수까지 따지면 모든 수의 약수 배수는 모든 수가...
-
뭔가 아 됐다 싶은 강의는 나름 풀이 체제가 잡히는 느낌인데 아닌 거는 진짜...
-
진로 원서 취업 학교생활등 다 괜찮습니당
-
이게 보통인거같기도.. 학과랑 완전히 같은분야도아니고 보통 대학가서 찾나 적성은
-
재수생이고 현역때 생1 지1 수능 개말아먹고 투사탐(사문 세지) 하려고 하는데 둘...
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
고려대경영 고려대식품공 어디가나음
-
신기하군뇨
-
정을선전에서 개털리고 갑민가 어버버했는데 원본 읽고 풀기만해서는 나는 개털린다는거 깨달았네요 ㅅㅃ
-
앞으로 이런 문법적인 부분을 ‘시경외‘하지 말도록 합시다
-
공스타 시작.. 2
사수까지 하다보니…뭔가 새로운 즐거움을 찾고 싶어 공스타 개설 했다는.. 사수해서...
-
대부분 저거보다 많이 썼을건데 대충 1년에 천만원 잡아도 초중고 12년동안 니들한테...
-
https://youtu.be/2b1IexhKPz4?feature=shared...
-
전적대는 건대임
-
늦버기 3
잘잤다
-
진학사 8칸 0
진학사는 8칸이었는데 학교홈페이지에 성적넣어보니 추합으로 뜨네요 ㅡㅡ; 이거...
-
얼부기 2
수면패턴 정상화
-
수12 확통하는데 매일 문제를 풀려고 하거든요 각각 하루에 몇문제씩은 꼭 푸는 게...
고능아ㄷㄷ