'17471' 태그의 글 목록

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 0) 준비물 최소 차이를 저장할 int 형 변수 minChai = Integer.MAX_VALUE 인접리스트 graph[] 1) 조합으로 N개중 1개~N/2 개 뽑는 모든 경우를 구한다. 2) 1)에서 나온 조합으로 팀을 가른다. 3) 갈라진 팀이 연결되어있지 않다면 다음 조합으로 넘어간다. 4) 갈라진 팀이 연결되어 있다면 각 팀의 인구수 차이를 구하여 최소 차를 갱신한다. 5) 모든 경우에서 가장 작은 최소차..

Algorithm 2021. 8. 12. 01:46

이전 1 다음