> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/2.md).

# 게리 맨더링2

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

문제 접근 방법

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

알고리즘

&#x20; 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번까지 돌면서 최댓값과 최솟값을 구해서 차이 빼면 된다!