크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
!!
-
재수강할까요?? 올해 8월쯤 노트필기도 다해가면서 보긴했는데
-
옳게 된 오르비언
-
와 내 교실이 아니라 실제 다른 학교에서 치니까 수능 실감이 엄청났음 이제 내년...
-
이게 바로 옯언의 자세지 ㅇㅇ
-
운동은재밌기에
-
계산이 엄이여서 풀면서 이게 맞나. . ? 싶었는데 계산으로 밀어붙이니 풀려씀...
-
이거 내가 주문해가지고 입힘 ㅋㅋㅋㅋ 좋더라 너희들도 한번 해봐라
-
정상인게 아닐까
-
명지대 문과 818.5 나옵니다 명지대 과 중에서 가능한 과 있을까요??ㅠㅠ 그리고...
-
진짜 다 갔네 9
-
ㄹㅈㄷㄱㅁ ㅊㄷ
-
서성한 자연대 ㅆㄱㄴ이라던데 이거 구라핑 맞죠? 저희학교 서울권 ㅈ반고긴 한데 올해...
-
뇨뇨이 0
뇨
-
할수있다
-
내일 컨설팅이네 3
기대된다아
-
헬스끝 2
야무지다
-
인하vs과기 2
인하 자연자전 과기 경영, 공대 복전혹은 전과준비할거
-
하하하
-
농담입니다~ㅋㅋ
-
제가 12중부터 공부해서 고전시가 먼저 수강해서 고전시가 마지막강좌만 남고 수국김을...
-
햇살론 대출받을까 했는데 오르비 아이민 입력해야해서 포기함
-
그래도 가능성 있을까요..? 8명 뽑는데 등수 보니까 5등이긴 하다만.. 하 ㅠ
-
반수생입니다 사회 돌아가는 원리가 궁금하고 사회를 바라보는 시선? 통찰력?을 얻을...
-
이브날에 놀지 오늘 놀아? ㅋㅋ
-
헬스장사람개많네 3
무슨일?
-
과탐 선택 2
생2 지1 할까 했는데 대성 패스만 구매했어서 메가 백호쌤 단과 구매해야하나 고민도...
-
당근할아버지 3
당근을 뺏으면 그냥 할아버지
-
부모님과 함께 ㅇㅇ
-
맛있는 음료수 4
닥터페퍼
-
왜클릭
-
제가 나이가 좀 많고 수능에서 커하를 찍기도 해서 이번에 꼭 가야 하거든요ㅠㅠ...
-
그래서 자제함..
-
ㅋㅋㅋ
-
수요가 잇음?
-
이 점수로 메디컬 붙을리가 없잖아...ㅠ
-
다시 들어옴 5
춥다..
-
분명히 난 시발점이랑 개념의 나비효과 들으려고 했는데 2
유튜브에서 강민철이랑 조정식이 서로 디스하는거 보고있네…
-
현역 : 설교,경희공 재수 : 수학 지구빼고 씹망 삼수 : 연고공, 한양높공 사수...
-
1. 중대 논술합격 검색 2. 합격되어있음 3. 감격의 눈물 4. 집안도 신남 5....
-
안녕하십니까 저번 글...
-
킥오프 파데했는데 하.. 어려워서 죽고싶음 내가 갸빡대가리겠지 진짜 죽고싶다. .
-
블랙리스트오른적 있음 ㅋㅋ 막 내 아이민가지고 부검하고 메모장에 적어놓더라
-
문득 생각난건데 12
작년에 저때문에 상처받으신분들께 다시금 이자리를 빌어 사죄드립니다 민폐끼친점 송구스럽습니다
-
오르비 같이 하자
-
뭐지 옆 학교들은 다 있는데 개명 전 이름으로 쳐도 안 나오고 당황스럽다
-
태그에도 없는 20세기 사람이 있다고?
ㄷㄷ