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
- Graph Cost
- 1557
- 카카오 API
- Hello 2023
- 앳코더
- vue3
- Codeforces Round 831 (Div. 1 + Div. 2)
- vue-google-login
- 카카오 로그인
- list_display
- 2022
- django
- 인하대 프로그래밍 경진대회
- 리버싱
- dart
- expand item
- Round 866
- 넥토리얼
- Div. 2
- 밑바닥부터 시작하는 딥러닝 1
- shake!
- 코드포스
- 레지스터
- Flutter
- Good Bye 2022: 2023 is NEAR
- iupc
- 알고리즘 대회
- E - Hanging Hearts
- idpiframe_initialization_failed
- 기본키 변경
Archives
- Today
- Total
목록Codeforces Round 831 (Div. 1 + Div. 2) (1)
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] 를 더한 값은 분리..
알고리즘/알고리즘 문제풀이
2023. 6. 10. 16:52