RectangularGrid

Code

public class RectangularGrid

{

    public long countRectangles(int width, int height) {

        long res = 0;

        for(int i = 0; i < height; i++) {

            for(int j = 0; j < width; j++) {

                if(i == j) continue;

                res += (height-i) * (width-j);

            }

        }

        return res;

    }

}

Problem

격자 무늬에서 직사각형의 개수를 구하라. (정사각형 제외)

예) 3x3 격자에서 1x2 직사각형은 12개, 1x3 직사각형은 6개, 2x3 직사각형은 4개이며 총 직사각형 개수는 22개이다.

__ __ __

|__|__|__|

|__|__|__|

|__|__|__|

Explanation

1 ≤ a ≤ height, 1 ≤ b ≤ width인 a x b 직사각형에 대한 공식을 찾으면 문제는 쉽게 풀린다.

1x2 개수는 height*(width-1), 1x3 개수는 height*(width-2)이다.

2x1 개수는 (height-1)*width, 3x1 개수는 (height-2)*width이다.

이를 통해 a가 i 증가하면 (height-i)*width, b가 j 증가하면 height*(width-j)인 공식을 찾아낼 수 있다. 두 공식을 합치면 (height-i) * (width-j)이고 모든 a x b 직사각형 개수를 구할 수 있다.