C++로 부등식 x² + y² < N을 만족하는 음이 아닌 정수 쌍 개수 구하기

문제 개요

양의 정수 N이 주어졌을 때, 부등식 x² + y² < N을 만족하는 음이 아닌 정수 쌍(x, y)의 개수를 구하는 것이 목표입니다.

해결 방법은 간단합니다. x를 0부터 x² < N을 만족하는 범위까지, y를 0부터 y² < N을 만족하는 범위까지 순회하면서 각 조합마다 x² + y² < N을 만족하는지 확인하고, 만족한다면 쌍의 개수를 하나씩 증가시키면 됩니다.

예제

입력: n = 4
출력: 고유한 쌍의 개수 = 4
설명: (0,0), (1,1), (0,1), (1,0) 네 쌍이 모두 x² + y² < 4를 만족합니다.

입력: n = 2
출력: 고유한 쌍의 개수 = 3
설명: (0,0), (0,1), (1,0) 세 쌍이 모두 x² + y² < 2를 만족합니다.

접근 방법

• 정수 변수 N에 양의 정수를 저장합니다.
• countPairs(int n) 함수는 n을 입력으로 받아 부등식 x² + y² < n을 만족하는 음이 아닌 정수 쌍의 개수를 반환합니다.
• count 변수는 조건을 만족하는 쌍의 개수를 저장하며, 초기값은 0입니다.
• i = 0부터 i² < n까지, 그리고 j = 0부터 j² < n까지 이중 반복문을 수행합니다.
• i² + j² < n이면 count를 1 증가시킵니다.
• 반복이 끝나면 count를 결과로 반환합니다.

C++ 코드 예제

#include <iostream>
using namespace std;
int countPairs(int n){
    int count = 0;
    for (int i = 0; i*i < n; i++)
        for (int j = 0; j*j < n; j++) //x*x + y*y < n
            if(i*i + j*j < n)
                count++;
    return count;
}
int main(){
    int N=4;
    cout << "Distinct Non-Negative integer pairs count: " << countPairs(N);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Distinct Non-Negative integer pairs count: 4

복잡도 분석

바깥쪽 반복문은 i² < n인 동안, 안쪽 반복문은 j² < n인 동안 실행되므로 각각 최대 √n번 수행됩니다. 따라서 전체 시간 복잡도는 O(n)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.

참고로 이 방법은 (0,1)과 (1,0)처럼 순서가 다른 쌍도 서로 다른 쌍으로 계산하는 순서쌍 기준의 카운팅 방식입니다. 만약 순서를 구분하지 않는 조합만 세고 싶다면 내부 반복문을 j = i부터 시작하도록 수정하면 됩니다.