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
- shake!
- Round 866
- 코드포스
- 밑바닥부터 시작하는 딥러닝 1
- 1557
- 카카오 로그인
- Codeforces Round 831 (Div. 1 + Div. 2)
- 넥토리얼
- vue-google-login
- vue3
- dart
- 레지스터
- E - Hanging Hearts
- list_display
- 리버싱
- django
- Good Bye 2022: 2023 is NEAR
- iupc
- Graph Cost
- 알고리즘 대회
- idpiframe_initialization_failed
- expand item
- 인하대 프로그래밍 경진대회
- 앳코더
- 카카오 API
- 기본키 변경
- 2022
- Div. 2
- Hello 2023
- Flutter
Archives
- Today
- Total
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] 이고 추가할 수 있는 개수는 dp[k + 1] / k * k 이다. 한 번에 k개 씩만 추가할 수 있다고 했으니까 내림을 해야 한다. 그리고 사용하는 연산의 수를 작게 해야 하므로 큰 수부터 가져가는 것이 이득이다. dp 배열이 내림차순(어쨌든 k가 작으면 n/kC2는 증가하니까 내림차순 아닐까)이니까 큰 것부터 선택하는 것이 이득이다? ( 그런 것 같다 )
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
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 |
Hello 2023 E. Anya's Simultaneous Exhibition (0) | 2023.01.07 |
Hello 2023 (2) | 2023.01.04 |
Good Bye 2022: 2023 is NEAR (0) | 2023.01.04 |
Comments