[BOJ][Java] 백준 9616번: 홀수 정사각형

1일 1PS 23일차!

📚 문제

---

골드 1

• 여담으로 Java 코테가 있어 일주일 간 Java 로 진행한다.
• 수학이라 생각만 할 수 있다면 쉬운 문제이다.
• 넓이가 홀수가 되는 경우는 한 변의 길이가 루트(홀수) 가 되는 경우이다.
• 이는 즉 변의 길이를 구할 때 a^2 + b^2 이 홀수가 되어야한다.
  • 정사각형의 꼭지점은 격자 위에 있기에 한 변의 길이를 포함하는 직사각형이 홀수, 짝수 길이로 이루어져야한다.
  • (1, 0), (1, 2), (3, 4) (3, 6) …
  • (1, 2) 를 변으로 가지는 정사각형은 (1 + 2) 의 길이의 정사각형 안에 딱 맞는 것을 쉽게 확인할 수 있다.
  • 즉, 한 변의 길이가 홀수인 정사각형에서 넓이가 홀수인 정사각형이 발생한다.
  • 이때 발생하는 정사각형은 (n, 0), (n-1, 1), (n-2, 2) … (0, n) 인데, (n, 0) 과 (0, n) 은 같은 모양이므로 총 n -1 개의 정사각형이 만들어진다.
• m, n 길이의 정사각형에 l 길이의 정사각형의 개수는 (m - l + 1) * (n - l + 1) 개 이다.
• 입력 정수의 크기로 인해 Long 타입으로 받아야한다.

💡 포인트

---

1. 1 부터 min(m, n) 까지 루프를 돌며 개수를 체크한다.
2. i 길이의 정사각형이 포함될 수 있는 개수 * i 길이 정사각형에서 나오는 홀수 정사각형 개수를 매번 더한다.

💻 코드

---

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 result = 0;
            for (long i = 1; i <= Math.min(m, n); i += 2) {
                result += (m - i + 1) * (n - i + 1) * i;
            }

            System.out.println(result);
        }

    }
}