크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
김과외에 선생님 찾기에서 자기 중/고등학교 이름 입력해보면 됨
-
갖고싶다
-
나도 내 재능 뛰어나다고 자부하고 있었는데 진짜 천재들 만나보니까 난 범부임을...
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 0
https://xurl.es/4stnb
-
내 얘기이긴한데 입시 끝나면 ~~해야지, ~~공부해야지 했던 것들이 n년씩 계속...
-
언랭처럼 공부에 뜻이 없는 사람들도 많다고 하지만 그 사람들 중에 음미체나 사업...
-
왜 다 긁혀있어
-
-
특정완료 각인가
-
사실 최상위 찍어본 사람들은 대부분 하는말이긴 해요 저 의대생 분이 조금 더 많이...
-
어 형은 4
시간당 25만원 과외를 해봤어
-
상위 10%인게 아닐까 노베 커트라인 끌어올리기는 옯평 ㅋㅋ
-
??
-
어 형은 0
현강 못다니고 라이브반만 들을듯
-
나만인강안들음? 1
고1때 EBS인강 들은거 말곤 인강 안들어봄 학교가면 학교쌤들이 현강해주는데 굳이? 싶어서
-
오히려 공부만 하느라 시야가 좁아져서 세상을 편협하게 보고 지식 너머의 지혜는 쌓을...
-
꼬우면 처속7등급 달고 인현강 0개로 공부해보던가ㅋㅋㅋㅋㅋㅋ
-
그래 넌 의대가는 게 맞다…. 일반대학 가서 일반기업 들어가면 어케될지 아찔하긴해
-
크아악 긁혀버렷..
-
최저준비하면서 내신이 완전 안정권은 아니라 2학기 휴반하면 정시까지 같이...
-
사긴 삿는데 안쓸것같아서 그냥 팔려고 하는데데얼마저옫 받고 파는게 적당할까요
-
난 실패한 인생이지만 행복하고 싶다고
-
-
뭐 요즘 의뱃 대환장 파티라도 열렸음?어떻게 하루도 쉬고 가는 날이 없냐
-
돈 없어서 현강 못 듣는 애들도 한트럭인데
-
못 이룬 게 병신은 아님뇨
-
그게 없어서 의지가 있건말건 결과물 못내놓는 대다수 사람들 싸그리 병신취급하는거 좆같긴 함
-
어깨 48cm 2
ㅁㅌㅊ?
-
한글? 어도비?
-
과외 제안서 보내다가 문득 궁금해져서 학생계정 하나 만들어봤는데 학생 상세정보 다...
-
여기 오래 있으면 자존감 개박살나서 우웅증 걸릴거 같음..
-
점공 결과 6
진학사 메가 표본 다 합친건데 합격하겠죠..?
-
ㅇㅇ
-
냐옹 8
그르릉 애옹
-
-
많이 어려움 답지 1~2시간 뒤에 올려드림요
-
메가스터디에 0
패스 59만3천원(56만원+이자 3만3천원) 교재값 318000원 패스교재 합치니 911000원이네
-
근데 공부에 관심 없는 건 아님
-
(중국 기준 송나라, 한국 기준 고려 이전 시대에서) 한국사 관련 묘지명이 사료로...
-
본인이 있는 세상이 전부고 나머지는 떨거지 버러지라 생각하는 게 진짜 문제임 내가...
-
점공 고속 1
지금 점공상태에서도 고속써서 빠질지 안빠질지 볼수있나요
-
-
작수 물지 94 94에서 생윤사문으로 런쳤는데 생윤 개념 엇캐 공부해야될지 감도 잘...
-
수학 선행에 있어서 고민입니다 . 공통은 이미 끝냈고 수1 수2 일품도 끝냈습니다...
-
전자는 최초합 후자는 추합 이유도 적어주세용 ㅎㅎ
-
공부에 뜻있는 사람들이 모인 시대재종에서 1년동안 다같이 으쌰으쌰 공부했을때 낸...
-
개념 몇 회독 후 기출붐석 강의 듣는 건가용? 그리고 제가 혼자 기출 1회독 하구...
-
저에 관한 정보 4개입니다. 그러나 하나는 거짓입니다. 한번 찍어보세요
-
정보) 현재 난리난 테 무 x 네이버페이 대란 요약.jpg 2
https://xurl.es/4stnb
-
25학년도 수능 동아시아사 4번 문제에 대한 간단한 고찰 2
안녕하세요. 요 며칠 새 동아시아사 개념서 관련하여 게시글을 썼던 강사...
고능아ㄷㄷ