https://www.acmicpc.net/problem/30807
문제 요약
- 범위 형의 간선 크기를 갖는 그래프가 주어지고
- 특정 비용을 갖는 MST를 만들 수 있는지 묻는 문제
- N : 20만
접근법
- 직관적으로 모든 간선이 최소이면 MST의 비용도 최소, 모든 간선이 최대이면 MST의 비용도 최대임을 알 수 있음
- 최소 ~ 최대 사이의 모든 MST 비용은 얻을 수 있을 것 같음(계단식 단조 증가 그래프 같은 것이 나올 것 같음)
- 뭔가 한칸씩 움직이면 비용을 얻어 낼 수 있을 것 같았음
- 해맸던 부분은 특정 간선의 크기가 변하면 그래프의 모양도 변할텐데 어떻게 구할지 몰랐음 => 한칸씩 무엇을 움직일지??
- 해설을 참고 했고, 핵심은 생각보다 간단했음
- 어딘가 간선이 1 증가하면 이전의 MST와 비용이 같거나 1 증가하거나
- 연쇄적으로 생각해보면 아무 간선이나 1씩 증가시키면 최소부터 최대까지 모든 MST를 구할 수 있음 => 이분탐색으로 해결
newbieski