BOJ 9616 - 홀수 정사각형

 

 

문제 링크

• 9616번: 홀수 정사각형 (acmicpc.net)

 

문제 풀이

 

자 문제에서는 $N, \; M$을 주지만, 일단 $N$과 $M$에 각각 1씩 더해서, $N \times M$ 격자점에서 사각형을 만드는 것으로 바꾸자.

 

일단 쉽게 한 변의 길이가 홀수인 정사각형을 평면에 맞게 평행하게 몇 개 만들 수 있는지부터 계산해 보자.

 

한 변의 길이가 $2i - 1$인 정사각형은, 격자점이 총 $(2i) \times (2i)$개가 필요하다. 

 

그리고 수식으로 나타내면, 가로로는 $N - 2i$ 번, 세로로는 $M - 2i$번 움직 일 수 있다.

그리고 한 변이 먹는 격자점은 $2i$개 이므로, 이것이 $N$ 이나 $M$을 초과 하면 안 된다.

$$2i \leq \min(N, M)$$

$$i \leq \bigg\lfloor \frac{\min(N, M)}{2} \bigg\rfloor \quad \quad K = \bigg\lfloor \frac{\min(N, M)}{2} \bigg\rfloor$$ 

$$\begin{aligned}
&\sum_{i=1}^{ K } \; (N-2i + 1)(M-2i + 1) \\
= &\sum_{i=1}^{ K } \;4i^2 - i\big(4+2M+2N \big) + \big(NM + N + M + 1 \big)\\
= \; & \frac{4K(K+1)(2K + 1)}{6} + \frac{K(K+1)(4+2M+2N)}{2} + K\big(NM + N + M + 1 \big)
\end{aligned}$$

 

자.. 이게 평행하게 했을 경우에 나올 수 있는 경우이다. 이제... 평행하지 않게 하는 경우에 대해 서술하겠다.

 

다음과 같은 꼴의 사각형을 만들어야 한다. 다음 사각형의 넓이는 $a^2 + b^2$ 이며, 이게 홀수가 되기 위해서는, 둘 중 하나는 짝수 하나는 홀수를 만족해야 한다. 변의 길이가 $a+b$을 먹으므로, 격자점은 $a+b+1$개 필요하다.

 

위의 식과 마찬가지로 비슷하게 도출해 볼 수 있다. 변의 길이가 $L$을 차지 할 경우, 격자점은 $L+1$개 필요하고,

가로로는 $N - (L+1)$번, 세로로는 $M - (L+1)$번 움직일 수 있다.

 

$a$가 홀수, $b$가 짝수 일 때, 될 수 있는 경우 $(a, b)$를 매트릭스 형태로 나열해 보자.

\begin{bmatrix}
(1, 2) & (3, 2) & (5, 2) & (7, 2) & \cdots  & (2k -1, 2) \\ 
(1, 4) & (3, 4) & (5, 4) & (7, 4) & \cdots  & (2k -1, 4) \\ 
(1, 6) & (3, 6) & (5, 6) & (7, 6) & \cdots  & (2k -1, 6) \\ 
\vdots & \vdots & \vdots & \vdots & \ddots  & \vdots \\ 
(1, 2y) & (3, 2y) & (5, 2y) & (7, 2y) & \cdots  & (2k -1, 2y) \\ 
\end{bmatrix}

 

잘 보면, 오른쪽 대각선 방향 $\nearrow$ 으로 있는 순서쌍 들이, 필요한 변의 길이가 같음을 볼 수 있다..!

관찰을 잘해보면, 한 변의 길이가 3이 드는 순서쌍은 한 개, 한 변의 길이가 5가 드는 순서쌍은 2개 이런 식이다.

 

한변의 길이는 $2i + 1 \;\; (1 \leq i)$ 인 정사각형은 $i$개 존재함을 알 수 있다. 각 정사각형마다, $2i + 2$개의 격자점이 필요하고, 이것은 $2i + 2 \leq \min(N, M)$ 을 만족해야 한다. 

$$\begin{aligned}
2i + 2 &\leq \min(N, M) \\
2i &\leq \min(N, M)-2 \\
i &\leq \frac{\min(N,M)- 2}{2}
\end{aligned}
\quad \quad \quad K = \bigg\lfloor \frac{\min(N,M)- 2}{2} \bigg\rfloor$$

 

\begin{aligned}
&\sum_{i=1}^{K} \; 2i\big(N-(2i+2) + 1\big)\big(M-(2i+2)+ 1\big)\\
= &\sum_{i=1}^{K} \; 2i\big(  N -2i -1\big)\big(  M -2i -1\big) \\
= &\sum_{i=1}^{K} \; 2i\big(  4i^2 + i(4 -2N -2M) + (NM -N -M + 1)\big) \\
= &\sum_{i=1}^{K} \; 8i^3 + 2i^2(4 -2N -2M) + 2i(NM -N -M + 1) \\
= \;&8\bigg( \frac{K(K+1)}{2} \bigg)^2 + \frac{2K(K+1)(2K+1)(4 -2N -2M)}{6}  + \frac{2K(K+1)(NM -N -M + 1)}{2}
\end{aligned}

 

이렇게 우리는 $N$과 $M$을 받아, 각각 1을 더해 준 뒤, 두 경우를 더해 정답을 제출하면 된다.