크리스마스 트리 꾸미기
사실 이건 아니고 백준 문제임
[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
-
공대 어느정도 갈 성적이에여?? 경희대 시립대 정도인가요?
-
“40년전 무임승차 이제야 갚아요” 부산역에 200만원 놓고 사라진 여성 0
40년 전 기차에 무임승차한 여성이 부산역에 200만 원을 놓고 사라졌다. 24일...
-
자연계열 어디까지 가능? 기공, 물리 생각중
-
전남의대 05학번 가정의학과분은 언제 가실련지..
-
맛없어요!! 마트에서 가성비샴페인사서 그런가
-
ㅇㅇ
-
왜조용함? 4
다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어디감?다어...
-
"정시"로 대학 못갔으니까 "늦게" 가면 되는데 ㅋㅋㅋㅋㅋㅋ
-
ㅇㅇ... 클쓰 후로 최종컷에 수렴함?...?
-
는 어그로구요 학고반수해서 다른 곳으로 옮길 예정인데 학고반수 하기 전 오티만...
-
내가 걔보다 못한게 뭔데... 시발진짜뭔데내가 어? 어? 어? 응?
-
7시되니까 딱 지옥철 풀리노 강남역지나와서 그런가
-
98 92 2 79 99가성대경영5칸인데 92 90 2 92...
-
너무 오바인가
-
으흐흐..
-
삼육약이 전통이 있다고 들었는데 어디가 괜찮을까요??
-
하시발 9
유니야 나 좀 믿어봐도 되겠니
-
458 ㅁㅌㅊ 4
-
진짜 예능,방송,음악활동,기타 활동 여러가지 등등 다 참여해서 다른 부문으로 인기를...
-
솔직히 경쟁사 하나만 있어도 서비스 2배는 좋아질듯..
-
테레비에서 하고 있는데 볼 만해
-
학창시절 내신에 손놓고 정시공부해서 내신은5~8등급 모고수능은1~2등급인데 서울대는...
-
광운대 전남대 세종대 10
광운대 건축, 세종대 공과계열, 전남대 기계 다 기숙사 살아야 합니다 님들은...
-
몇 명 더 들어오면 칸수 훅 떨어지고 나가면 훅 올라가고
-
변표 뜨고 6칸 초반에서 5칸 초반 됐는데 불안하다 너무
-
유대종, 강윤구 풀커리 타고 26 수능 도전해봅니당 3
약 N년 전에 현역으로 대학 갔던 아저씨입니다. (그래도 2000년대임...)...
-
보통 이런곳에서 빵나나요? 아니면 마지막날쯤 우수수 들어오나요?
-
30명 넘게 뽑아서 불확실성은 좀 덜한 대신 3칸에서 5칸으로 갑자기 오른 게 계속...
-
좀 ㅍ해주세오ㅠㅠ
-
감사합니다 한양대 ㅠㅠ
-
정시 라인 0
언미영생1지1 93/92/2/87/91 수시 다 떨구면 진학사 사려해서 라인 같은...
-
표본분석 시작 0
표본분석 시작하려고하는데 표본분석이 앞 등수 애들이 실제로 어디갈지 보는...
-
낙지 설대컷 조금씩 내려가네요 더 빨리 내려가라~~
-
기만자들
-
으흐흐..
-
인하대 대형과 진학사 서비스 시작부터 6칸 최초합~추합 왔다갔다 하는데 안심해도...
-
아 미쳐버리겠네 1
충북대 의대는 진짜 못믿겠는데 시발진짜 아니 주차장드립을 저거를 어케 받아주지 아제발씨발
-
학교라인 하나차이면... 어떤게 더 좋을까요...?
-
중앙대 기계공학과입니다. 최초 모집인원 68명인데 44등이고 칸수는 6칸입니다....
-
울고있어요
-
에너지공학과 0
고대 융합에너지 , 성대 에너지 등 에너지공학과는 공대 중에서 취업 기준으로 봤을...
-
고대식 점수 2
664.63이었는데 업뎃 되고도 0.01점도 안바뀌었네요..
-
내가 ㄹㅇ 유빈이가 뭔지 궁금해서 텔그를 깔았는데 이게 엄마한테 니 자녀가 텔그를...
-
연대는 진짜 심각하네 13
적정표본수채운건 거의 보이지도않고 대부분학과가 1배수 겨우돌거나 1배수도 못채움...
-
학과 대부분이 22,23학년도에 비해 추합인원 혹은 비율이 적은데 이유가 뭔가요?
-
저도이제대학생이에요
-
진학사 고대 1
지금 진학사 업데이트 고대 변표 반영된건가요?
-
크리스마스 이브 잘 지내세요 메리 크리스마스
ㄷㄷ