사각형 수 세기

n개의 행과 m개의 열로 이루어진 사각형 격자 모양이 있다. 이때, 여기서 만들어지는 사각형의 수는 총 몇개인가?

일단 n개중에 k개를 선택하는 문제가 된다. 단, 이 경우 k개가 연속되어 있어야 한다는 조건이 발생한다.

이 경우에, n-k+1개의 선택이 가능하다. 가령, 10개중에서 3개를 선택하는 경우에는 7가지 선택이 가능하다.

이 논리는 행과 열 모두에 적용 가능하다. 가령 n행중에서 k개의 행을 선택한 후, 각 경우에 대해서 m개의 열 중 j개의 열을 선택할 수 있다.

(n-k+1) * (m-j+1)을 k와 j에 대해서 다 더하면 된다. k는 1부터 n까지, j는 1부터 m까지 더하면 된다.

수열 두개를 곱해서 더하는 경우에 대해 그닥 고민할 필요는 없다. k에 대한 합은 n(n+1)/2이고 j에 대한 합은 m(m+1)/2이다. 나머지는 상수이므로 n과 m을 각각 곱해주기만 하면 된다.

(n*n-n*n/2-n/2+n) * (m*m-m*m/2-m/2+m) = n(n+1)*m(m+1)/4

간단하게 끝나버렸다.

이 공식이 맞는지 한번 점검해보자.

2행 3열의 사각형 격자가 있다고 하면 여기서 나오는 사각형은
1칸짜리 = 6개
2칸짜리 = (세로 4개) + (가로 3개) = 7개
3칸짜리 = 세로 2개
4칸짜리 = 2개
5칸짜리 = 없음
6칸짜리 = 1개
6+7+2+2+1 = 18개

잘 맞는다.


갑자기, 친구가 물어봐서 올려둠.