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
- Good Bye 2022: 2023 is NEAR
- Graph Cost
- iupc
- 코드포스
- 넥토리얼
- 앳코더
- shake!
- 2022
- 카카오 로그인
- list_display
- 리버싱
- Codeforces Round 831 (Div. 1 + Div. 2)
- idpiframe_initialization_failed
- 알고리즘 대회
- 카카오 API
- 밑바닥부터 시작하는 딥러닝 1
- vue-google-login
- dart
- vue3
- E - Hanging Hearts
- 1557
- Div. 2
- Flutter
- 기본키 변경
- Hello 2023
- expand item
- 레지스터
- django
- 인하대 프로그래밍 경진대회
- Round 866
Archives
- Today
- Total
목록Graph Cost (1)
pseong
Codeforces Round #841 (Div. 2) E. Graph Cost
Problem - E - Codeforces codeforces.com Solution. 간선의 가중치가 k인 간선의 개수를 dp[k] 라 하자. 간선의 가중치는 연결된 두 노드의 최대 공약수 이므로 최대 공약수가 k가 되려면 두 수는 k의 배수가 되어야 한다. 따라서 k의 배수 중에서 2개를 선택하는 경우의 수 n/kC2를 구해주면 dp[k]의 초기값을 설정할 수 있다. 하지만 k의 배수 중에서 2k의 배수중에서 2개를 선택한 경우의 수는 최대공약수가 2k이므로 제외해 주어야 하고 마찬가지로 3k, 4k... 쭉 제외해 주어야 한다. 따라서 n부터 1까지 반대로 dp[i]를 채워 주면 답을 구할 수 있다. k를 선택했을 때 최대 공약수가 k + 1 인 추가할 수 있는 간선의 개수는 dp[k + 1] 이..
알고리즘/알고리즘 문제풀이
2023. 1. 8. 02:13