BOJ 2203 - 선거구 나누기

무작위화가 정해..?

 

오름차순 정렬을 통해 인원이 가장 적은 k개의 마을은 고려하지 말자. 

인원이 가장 적은 k개의 마을을 다른 도시에 넣는다고 더 좋은 결과를 보장하지 않음을 알 수 있기 때문에 남은 2k개의 마을에서 적절히 선거구를 나누는 방법을 사용하자. 선거구를 나누는 방법으로 무작위화를 사용하면 된다.

두 그룹으로 나눴을때 두 그룹 다 k*500을 만족하지 않는다면 계속 랜덤으로 배열을 섞어주는 방법을 사용하자. 

이 방법이 왜 될까?? 는 잘 모르겠고 제한이 작고 문제의 조건을 만족하는 배치가 꽤나 많이 존재하기 때문에 충분히 시간안에 높은 확률로 답을 구할 수 있음을 보장할 수 있다. 

 

신기한 문제