[백준] 9616. 홀수 정사각형

1. 문제 설명

격자 정사각형은 모든 꼭짓점이 격자점 위에 있는 정사각형이다. 격자점은 x좌표와 y좌표가 모두 정수인 점이다. 예를 들어, (1,5)는 격자점이지만, (1, 1.5)는 아니다.

m×n 격자 위에 격자 정사각형은 총 몇 개가 있을까?

위의 그림은 4×4 격자 위에서 찾을 수 있는 격자 정사각형의 일부이다. 그림 1, 2, 3과 같이 축에 평행한 격자 정사각형도 있고, 4, 5, 6과 같이 평행하지 않은 정사각형도 있다. 그림 2, 4, 6의 정사각형은 넓이가 짝수이고, 1, 3, 5는 홀수이다.

격자의 크기가 주어졌을 때, 넓이가 홀수인 격자 정사각형은 총 몇 개가 있는지 구하는 프로그램을 작성하시오.

두 격자 정사각형이 네 변을 모두 공유하지 않으면 다른 정사각형이다.

• 입력
  입력은 최대 50000줄로 이루어져 있다. 각 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100000) 입력의 마지막 줄에는 0이 두 개 주어진다.

• 출력
  각 입력마다 넓이가 홀수인 격자 정사각형의 수를 출력한다. 정답은 항상 64비트 정수(64-bit signed integer) 범위이다.

2. 문제 접근

$m \ X \ n$ 격자 내에 넣을 수 있는 정사각형 중 넓이가 홀수인 경우를 세는 문제입니다.

일단은 비스듬한 정사각형은 고려하지 않고 $l \ X \ l$ 정사각형을 채워 넣는다고 가정해 봅시다. 당연히
$l \ <\ m, n$ 이며 넣을 수 있는 $l \ X \ l$ 정사각형의 개수는 $(m-l+1)(n-l+1)$개입니다.

이제 $l \ X \ l$ 정사각형 내에 채워 넣을 수 있는 비스듬한 정사각형의 경우를 고려해 봅시다. 내부에 있는 정사각형의 넓이는 $(a+b)^2 - 4ab$ 입니다. $4ab$는 반드시 짝수이므로 $a+b$가 홀수여야 내부의 정사각형의 넓이도 홀수가 됩니다.

문제 조건상 네 변을 공유하지 않기만 하면 별도의 정사각형으로 카운트 하므로 한 변이 $k$인 정사각형 내에 들어가는 정사각형의 개수 역시 $k$개입니다. 따라서 $m \ X \ n$ 격자 내에 넣을 수 있는 변의 길이가 홀수인 정사각형의 개수를 구하면 답을 찾을 수 있습니다.

3. 코드

파이썬

def find_square(m, n):
    ans = 0
    for i in range(1, min(m, n) + 1, 2):
        ans += (m - i + 1) * (n - i + 1) * i
    print(ans)

while True:
    m, n = map(int, input().split())
    if (m == 0 and n == 0): exit()
    find_square(m, n)

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        while (true) {
        	st = new StringTokenizer(br.readLine());
            long m = Long.parseLong(st.nextToken());
            long n = Long.parseLong(st.nextToken());
            
            if (m == 0 && n == 0) {
                break;
            }
            
            long ans = 0;
            for (long i = 1; i <= Math.min(m, n); i += 2) {
                ans += (m - i + 1) * (n - i + 1) * i;
            }
            
            System.out.println(ans);
        }
        
    }
}

문제 분류가 DP긴 한데 변의 길이가 주어질 때 정사각형의 개수를 바로 구할 수 있으므로 별도의 DP 배열이 필요 없습니다.

역시 수학문제 풀때는 파이썬이 좋네요~ 형변환도 알아서 해주고 말이죠 ㅋㅋㅋㅋ
자바로 풀 때는 합의 범위에 유의합니다. 개수가 n^3에 비례하기 때문에 반드시 long으로 지정해줘야 합니다.

단순 누적합 문제이므로 m, n, l을 안다면 공식화 시켜서 한 번에 풀 수도 있습니다. 그러면 O(1)의 선형 시간 내에 문제를 풀 수 있습니다.