Codeforces Round #841 (Div. 2) E. Graph Cost

Problem - E - Codeforces

 

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는 증가하니까 내림차순 아닐까)이니까 큰 것부터 선택하는 것이 이득이다? ( 그런 것 같다 )