Q 6131 완전 제곱수

💡 문제 요약 및 분석

두 양의 정수 A와 B가 있다. (1 ≤ B ≤ A ≤ 500) 이 때, A의 제곱이 B의 제곱보다 N 만큼 크다는 조건을 만족시키는 쌍이 몇 쌍인가를 구하면 된다.

💡 알고리즘 설계

1. 반복문으로 [A=1, B=1], [A=2, B=1], [A=3, B=1] 등등… A,B 가 500이 될 때 까지의 모든 조합을 검사한다.

2. 반복문 안에서 A제곱 - B제곱 = N 이 되는 경우를 count 한다.

3. 반복문 종료 후 count 를 출력한다.

💡 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int count = 0;
        for (int b = 1; b <= 500; b++) {
            for (int a = 1; a <= 500; a++) {
                if (a*a - b*b == N) count++;
            }
        }

        System.out.println(count);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(1)	O(1)