25301번 - 새싹 서브태스크언어 제한함수 구현

바쿠는 정사각형 모양의 넓은 땅을 균등하게 구획을 나눠 작은 정사각형 밭을 $N \times N$개 만들 었다. 각 밭에 $P$개씩 씨를 뿌린 후 일주일 후에 보니 어떤 씨는 새싹이 났고 어떤 씨는 아직 새싹이 나지 않았다. 예를 들어, 아래 그림은 $6 \times 6$개의 밭에 $3$개씩의 씨를 뿌린 후 새싹이 난 모습을 나타낸다. 가장 왼쪽 위 밭에는 두 개의 새싹이 났고, 가장 오른쪽 아래 밭에는 한 개의 새싹이 났다.

밭을 둘러보던 바쿠는 최근에 배운 중간값(median)이 생각났다. 중간값은 홀수개의 주어진 값들 중 하나로, 주어진 값들을 정렬했을 때 정확히 가운데에 있는 값이다. 예를 들어, 다섯 개의 주어진 값이 $0, 1, 2, 2, 3$이라면 중간값은 $2$가 된다.

바쿠는 중간값과 평균이 얼마나 다를 수 있는지 궁금하여 각 밭에 난 새싹의 개수의 중간값과 평균을 비교해보려 한다. 다양한 경우를 살펴보기 위해 비교할 중간값과 평균은 정사각형 모양의 인접한 $K \times K$개 밭에 대해 구하도록 한다. 이렇게 하면 주어진 $N \times N$개 밭에서 총 $(N-K+1) \times (N-K+1)$번의 비교가 가능하다.

예를 들어, 위 그림의 밭에 대해 $3 \times 3$개 단위로 중간값과 평균을 모두 구해보면 아래 표와 같다. 가장 왼쪽 위의 $3 \times 3$개 밭에 난 새싹의 개수는 $2$개, $1$개, $0$개, $0$개, $1$개, $0$개, $2$개, $0$개, $1$개이므로 중간값은 $1$, 평균은 $7/9$이다. 가장 오른쪽 위의 $3 \times 3$개 밭에 대한 중간값은 $0$, 평균은 $8/9$이다.

중간값	평균

바쿠는 중간값과 평균의 차이의 최댓값을 구하려 한다. 위 예에서 최댓값을 갖는 경우는 아래 그림에서 붉은 정사각형으로 표시된 부분으로, 중간값이 $0$, 평균이 $1$로 두 값의 차이는 $1$이다.

	중간값	평균	차이

바쿠는 계산의 편의를 위해 중간값과 평균의 차이를 $K^2$배 한 값의 최댓값을 구하려 한다. 따라서 위 예에서 최댓값은 $9$가 된다. 여러분은 바쿠를 위해 다음 함수를 구현해야만 한다.

• int diff( int K, int[][] V ) ; 단 한번 호출되는 함수이다. $V$는 크기 $N \times N$인 배열(vector)이다. 각 밭에 난 새싹의 개수 $V[0..N-1][0..N-1]$이 인자로 주어진다. $K \times K$ 크기 단위로 찾은 중간값과 평균의 차이를 $K^2$배 한 값의 최댓값을 구하여 return 한다.

여러분은 sprout.cpp라는 이름을 가진 하나의 파일을 제출해야만 한다. 이 파일에는 다음의 함수가 구현되어 있어야 한다.

• int diff( int K, int[][] V ) ;

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론, 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

주어지는 그레이더는 다음과 같은 형식으로 입력을 읽는다.

• line $1$: $N$ $K$
  • $N$: 밭의 크기, $K$: 영역의 크기
• line $2+i$ ($0 \le i \le N-1$): $V_{i0}$ $V_{i1}$ $\cdots$ $V_{iN-1}$
  • $V_{i0}$, $V_{i1}$, $\cdots$, $V_{iN-1}$: $i$행의 새싹의 개수들

주어지는 그레이더는 여러분의 코드가 diff() 함수에서 리턴한 값을 출력한다.

• $1 \le N \le 2\,000$
• $K$는 홀수이며 $1 \le K \le N$
• $0 \le V_{ij} \le 30$ ($0 \le i, j \le N-1$)

• sprout_public.zip