Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- iupc
- Flutter
- shake!
- Round 866
- django
- 코드포스
- Div. 2
- vue-google-login
- Codeforces Round 831 (Div. 1 + Div. 2)
- 카카오 로그인
- list_display
- idpiframe_initialization_failed
- 인하대 프로그래밍 경진대회
- 밑바닥부터 시작하는 딥러닝 1
- 리버싱
- 레지스터
- 앳코더
- 1557
- E - Hanging Hearts
- 2022
- Graph Cost
- 알고리즘 대회
- expand item
- vue3
- dart
- Hello 2023
- 넥토리얼
- 카카오 API
- Good Bye 2022: 2023 is NEAR
- 기본키 변경
Archives
- Today
- Total
pseong
Codeforces Round 831 (Div. 1 + Div. 2) E - Hanging Hearts 본문
Problem - E - Codeforces
codeforces.com
보자마자 트리디피 인 것은 알았지만 한 가지 착각한 것 때문에 시간이 너무 오래 걸렸다.
dp[i] : i를 루트로 하는 서브트리 내에서 정답
이라고 했을 때 dp[i] 는 max(모든 자식 dp[j] 를 더한 값, max(dp[j]) + 1)이라고 생각했다.
여기서 간과한 사실은 이렇게 구현하면 max(dp[j]) + 1)에 포함된 노드들 중에 모든 자식 dp[k]를 더한 값이 존재할 수 있다는 것이다. max(dp[j]) + 1로 구한 값은 항상 그 자식들도 max(dp[k]) + 1로 구해져야 한다. 생각해 보면 max(dp[j]) + 1이라는 값은 트리의 깊이이다. 따라서 트리의 깊이와 모든 자식 dp[j] 를 더한 값은 분리해야 한다.
그렇다면 dp[i] = max(모든 자식 dp[j] 를 더한 값, 트리의 깊이)로 설정해야 한다.
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two (0) | 2023.06.04 |
---|---|
Codeforces Round 866 (Div. 2) D. The Butcher (1) | 2023.05.31 |
Codeforces Round #841 (Div. 2) E. Graph Cost (1) | 2023.01.08 |
Hello 2023 E. Anya's Simultaneous Exhibition (0) | 2023.01.07 |
Hello 2023 (2) | 2023.01.04 |
Comments