무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

올인원 [1117418] · MS 2021 · 쪽지

2024-12-24 12:44:40
조회수 536

크리스마스 트리 꾸미기

게시글 주소: https://i.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 (+1,000)

  1. 1,000

올인원 [1117418]

쪽지 보내기

글쓰기
오르비 1365942번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오늘의 추천 글

2026 수능D - 323

오르비 플레이

오르비 RARE

오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2024 Move Inc.

orbisoptimus (v17-7e2515)