양의 정수 N이 주어졌을 때, 부등식 x² + y² < N을 만족하는 음수가 아닌 정수 쌍(x, y)의 개수를 구하는 것이 이 글의 목표입니다. 여기서 (0,1)과 (1,0)처럼 순서가 다른 쌍은 서로 다른 쌍으로 계산합니다.
이 문제는 브루트 포스 방식으로 해결할 수 있습니다. x를 0부터 x² < N까지, y를 0부터 y² < N까지 순회하면서 각 조합마다 x² + y² < N 조건을 검사하고, 조건을 만족할 때마다 쌍의 개수를 하나씩 증가시키면 됩니다.
입력 및 출력 예시
예시 1
n = 4
고유한 쌍의 개수 = 4
설명: 조건을 만족하는 쌍은 (0,0), (0,1), (1,0), (1,1)입니다. 이 네 쌍은 모두 x² + y² < 4를 충족합니다.
예시 2
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
복잡도 분석
바깥쪽 반복문과 안쪽 반복문이 각각 약 √N번 실행되므로, 이 알고리즘의 시간 복잡도는 O(√N × √N), 즉 O(N)입니다. 공간 복잡도는 추가 배열 없이 카운터 변수만 사용하므로 O(1)입니다. N의 크기가 크지 않다면 충분히 효율적인 방법입니다.