BOJ 17441번: 파리채 만들기

미적분학에 나오는 Green의 정리에 대해 학습한 후, 이를 사용하는 알고리즘 문제가 있다고 해서 찾아서 풀어보았다. Green의 정리를 제대로 이해하고 있다면, 그걸 모르는 사람에게도 설명할 수 있어야 하므로, 독자가 Green의 정리를 모른다고 가정하고 글을 써보기로 했다.

 

문제 내용과 계산식

다각형 모양의 영역 R에 두 점 $P(x_1, y_1), Q(x_2, y_2)$가 있을 때, $PQ^2$의 기댓값을 구하는 문제이다. 연속적인 점의 위치에 대한 기댓값이므로 구하는 기댓값 E는 다음과 같이 적분으로 표현된다. 여기서 $dA_1=dx_1dy_1, dA_2=dx_2dy_2$ 이다.

$$E=\left ( \iiiint_{P, Q\in R} dA_1 dA_2  \right )^{-1}\times\iiiint_{P, Q\in R}\left ( (x_2-x_1)^2+(y_2-y_1)^2 \right )dx_1dy_1dx_2dy_2$$

영역 R의 넓이 A에 대해, 적분을 정리하면 다음과 같이 표현된다. 편의상 다중적분 기호는 적분 하나로 쓰고, 적분의 범위는 자명하므로 생략하였으며, P와 Q의 위치는 대칭적이므로 한 점에 대해서만 적분하고 나머지는 상수인 경우에는 첨자를 생략하였다.

$$EA^2=\int(x_1^2+y_1^2)dA_1dA_2+\int(x_2^2+y_2^2)dA_1dA_2-2\int x_1x_2dA_1dA_2-2\int y_1y_2dA_1dA_2$$ $$ EA^2 = 2A\int (x^2+y^2)dA - 2\left (\int xdA  \right )^2-2\left (\int ydA  \right )^2$$

두 번째 항과 세 번째 항은 질량 중심을 계산할 때 많이 계산해본 형태이다. 즉, 인접한 점 $P_i(x_i, y_i), P_{i+1}(x_{i+1}, y_{i+1})$에 대해, $\triangle OP_iP_{i+1}$의 부호 있는 넓이와 무게중심의 좌표의 곱을 다 더하면 된다.

$$\int xdA=\sum_{i=0}^{n-1}\left(\frac{x_i+x_{i+1}}{3}\times(x_iy_{i+1}-x_{i+1}y_i) \right )$$ $$\int ydA=\sum_{i=0}^{n-1}\left(\frac{y_i+y_{i+1}}{3}\times(x_iy_{i+1}-x_{i+1}y_i) \right )$$

첫 번째 항은 물리적으로 표현해서, 다각형의 면밀도가 1이라고 할 때 z축에 대한 주어진 다각형의 관성 모멘트이다. 이것을 어떻게 계산할까? 삼각형의 관성 모멘트들의 합으로 나타내도 되겠지만, 삼각형도 관성 모멘트는 적분 과정이 그리 쉽지만은 않을 것이다. Green의 정리를 이용하면 더욱 간단한 방법이 있다.

 

면적분을 선적분으로 바꾸기

첫 번째 항의 면적분을 놀랍게도 다각형의 둘레에 대한 선적분으로 바꿀 것이다. 먼저 $\int y^2dA$를 계산하자.

충분히 작은 x의 미분 dx에 대해, x부터 x+dx까지의 구간은 y1부터 y2까지 다각형 내부에 있다. 다각형의 모양에 따라서는 주어진 x 구간에 대해 다각형과 만나는 y 구간이 하나의 연속구간이 아닐 수도 있지만, 이는 나중에 고려하기로 한다.

 

$\int y^2dA$를 계산하려면, y에 대해 먼저 적분한 후에 x에 대해 적분해야 $ y^2$의 적분이 바로 계산되어 편리할 것이다. 그러므로 위 그림과 같이 x축을 기준으로 다각형을 잘게 나누자. x부터 x+dx 사이의 영역 R'에 대한 적분을 계산하자. $$\left(\int_{y_1}^{y_2}y^2dy \right )dx=\frac{y_2^3-y_1^3}{3}dx$$

이제 이를 모든 x에 대해 더하면 구하는 적분이 된다. 다각형의 둘레를 C라고 하자. 그리고 C의 방향을 시계 반대 방향으로 잡자. $$\iint y^2dA= \iint_{y_1}^{y_2}y^2dydx=\int\frac{y_2^3-y_1^3}{3}dx=-\frac{1}{3}\oint _C y^3dx$$ 여기서 주어진 x축에 수직인 직선과 다각형이 만나는 점이 두 개가 아니면 어떻게 하냐고 물을 수 있을 것이다. 이 경우에도 유한 개의 구간의 합이므로, 방향을 시계 반대 방향으로만 잡아주면 더해지는 부분은 왼쪽으로, 빼지는 부분은 오른쪽으로 지나가게 되어서 동일한 식이 성립함을 알 수 있다. 예를 들어 x좌표가 x인 점이 다각형 상에 4개가 있고, y좌표가 순서대로 y1, y2, y3, y4라고 하자. [y1, y2]와 [y3, y4]가 다각형 내부라면, 적분 식에서 y1과 y3은 빼지고 y2과 y4는 더해지면 된다. 여기서 y1을 거쳐서(오른쪽), y2로 다시 오고(왼쪽), 다시 y3을 거쳐서(오른쪽), y4로 와야(왼쪽) 하므로 부호가 모두 맞는다.

유사하게 $\int x^2dA$ 를 계산할 수 있다. 여기서도 매우 유사하므로 구체적인 과정은 생략하지만, 주의해야 할 점은 이번에는 더해져야 하는 부분이 위쪽으로 지나간다는 것이다. 따라서 음의 부호를 빼어서 $$\iint x^2dA= \frac{1}{3} \oint _C x^3dy$$ 이다. 결론적으로 첫 번째 항은 다음과 같이 계산된다. $$ \int (x^2+y^2)dA= \frac{1}{3} \oint _C x^3dy- \frac{1}{3} \oint _C y^3dx$$ 이 식은 각 유향선분 $ l_i: P_i(x_i, y_{i})\rightarrow P_{i+1}(x_{i+1}, y_{{i+1}}) $에 대해서 적분한 것의 합으로 구할 수 있으므로 문제가 매우 쉬워졌다. 선분을 매개변수 t로 $x=x_i+t(x_{i+1}-x_i), y=y_i+t(y_{i+1}-y_i), 0\leq t\leq1$로 두면, $$\int_{l_i}y^3dx=\int_{l_i}y^3(x_{i+1}-x_{i})dt=\int_{y_i}^{y_{i+1}}y^3\frac{x_{i+1}-x_{i}}{y_{i+1}-y_{i}}dy=\frac{y_{i+1}^4-y_i^4}{4}\times\frac{x_{i+1}-x_{i}}{y_{i+1}-y_{i}}$$ 그런데 $ y_{i}= y_{i+1}$이면 분모가 0이어서 안 된다. 이 경우에는 자명히 적분값이 $y_i^3(x_{i+1}-x_i)$이다. 이 두 결과를 종합하여 다음과 같이 쓰면 된다.$$\int_{l_i}y^3dx=(y_i^3+y_i^2y_{i+1}+y_iy_{i+1}^2+y_{i+1}^3)(x_{i+1}-x_{i})$$

따라서

$$\oint _C y^3dx=\sum _{i=0}^{n-1}(y_i^3+y_i^2y_{i+1}+y_iy_{i+1}^2+y_{i+1}^3)(x_{i+1}-x_{i})$$ $$\oint _C x^3dy=\sum _{i=0}^{n-1}(x_i^3+x_i^2x_{i+1}+x_ix_{i+1}^2+x_{i+1}^3)(y_{i+1}-y_{i})$$이며, 이를 원래 식에 대입하면 문제가 풀린다. 이 문제의 아이디어를 일반화한 것이 Green의 정리라고 하는데, 이는 Stokes 및 Divergence 정리와 함께 다음에 시간이 될 때 글을 올리도록 하겠다.