게리 맨더링2

문제 접근 방법은 맞았지만 긴가민가해서 하나도 구현하지 못했다.

문제 접근 방법

기준점(x,y)와 d1,d2를 모두 구해서 각각의 경우에서 최대 인구-최소 인구 차이의 최솟값을 구하면 된다. =>x:20 * y:20 * d1:20* d2:20 = 20*20*20*20 = 160000 << 1억 이므로 시간 안에 가능하다!

알고리즘

0. 각각의 경우에 대해 마킹할 배열 초기화

1. 5번 경계선 먼저 마킹

2. 5번 경계선 기준으로 1,2,3,4 선거구 경계선 마킹

3. 1,2,3,4 경계선 기준으로 안을 해당 선거구 번호로 채움

4. 각 선거구의 인구수 합산, 최대 인구와 최소 인구 수 구해서 최대 인구-최소 인구 차이 구함

5. 최대 인구-최소 인구 차이의 최솟값 구함

두번째 풀었을 때 틀린 부분

1. d2-for문 반복 조건 : x+d1+d2<=N-1 ❌ x+d1+d2<=N-2⭕️ ??왜?

2. 선거구 1,2,3,4 경계선 마킹할 때, 행고정/열고정시에 단순 x,y로 넣어버림, 1 : 행변함,열고정 : Mark[r][y], r 범위=x-1 ~ 0, x-- 2 : 행고정,열변함 : Mark[x+d2][c], c범위=y+d2+1 ~N-1, c++ 3 : 행고정,열변함 : Mark[x+d1][c], c범위=y-1 ~ 0, c-- 4 : 행변함,열고정 : Mark[r][y-d1+d2], r범위=x+d1+d2+1 ~ N-1

3. 각 선거구 별로 인구수 총합 구하기 : 2중 for문으로 마킹한 배열 Mark을 순회하면서 (r,c)의 선거구에 해당하는 인구수인 입력받은 Arr[r][c]를 합산해간다! people[Mark[r][c] += Arr[r][c] 5번 선거구 인구수는 1,2,3,4선거구 인구수를 합하고 남은 나머지 0으로 된 칸 갯수이다. 그렇기 때문에 Mark배열에서 0으로된 칸과 5로된 칸의 값을 더하면된다! 2중 for문으로 0과 5로된 칸의 값을 다 더했으면 2중 for문이 끝난 후에 둘을 합산하면 된다!!

4. 최대 인구, 최소 인구 구할 때, 3번의 2중 for문으로 각 선거구마다 인구총합을 먼저 구한 다음, 스코프 끝난 후에 minP와 maxP에 최댓값과 최솟값을 구한다!!!

5. 최대인구수 - 최소인구수 차이는 크기 6인 people 배열의 인덱스 1번부터 5번까지 돌면서 최댓값과 최솟값을 구해서 차이 빼면 된다!