정수 n이 주어졌을 때, 다음 두 조건을 동시에 만족하는 세 수의 쌍(트리플렛)을 찾아 그 개수를 세는 것이 목표입니다.
a2 + b2 = c2
1 ≤ a ≤ b ≤ c ≤ n
이 문제는 두 개의 반복문을 사용하여 해결할 수 있습니다. 첫 번째 반복문으로 1 ≤ a ≤ n 범위를, 두 번째 반복문으로 1 ≤ b ≤ n 범위를 순회하면서 c = √(a2 + b2)를 계산합니다. 그런 뒤 두 조건을 모두 만족하는 경우 카운트를 증가시키면 됩니다.
예제
입력 − N = 5
출력 − 트리플렛 개수 − 1
설명 −
a = 3, b = 4, c = 5일 때 두 조건을 모두 만족합니다.
입력 − N = 3
출력 − 트리플렛 개수 − 0
설명 −
조건 1과 2를 모두 만족하는 트리플렛은 존재하지 않습니다.
접근 방법
정수 N은 탐색 범위 [1, N]의 상한값을 저장합니다.
함수 countTriplets(int n)은 n을 입력받아 a2 + b2 = c2와 1 ≤ a ≤ b ≤ c ≤ n 조건을 만족하는 트리플렛의 개수를 반환합니다.
변수 count는 조건을 만족하는 트리플렛의 개수를 저장하며, 초기값은 0입니다.
변수 sum은 a와 b의 제곱합을 저장합니다.
a를 1부터 n까지, b를 a부터 n까지 순회하면서 sum = a*a + b*b를 계산하고, c를 sum의 제곱근(sqrt(sum))으로 구합니다.
계산된 c가 c*c == sum을 만족하고 b ≤ c && c ≤ n일 때, 즉 조건 1과 2를 모두 만족할 때
현재 a, b, c가 유효한 트리플렛이므로 count를 증가시킵니다.
a = n, b = n까지 위 과정을 반복합니다. 최종적으로 count에는 조건을 만족하는 트리플렛의 개수가 저장됩니다.
count를 결과값으로 반환합니다.
이 알고리즘의 시간 복잡도는 두 반복문을 사용하므로 O(n2)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int n){
int count = 0;
int a,b,c;
a=b=c=1;
int sum=0;
for (a = 1; a <= n; a++) //1≤a≤n{
for (b = a; b <= n; b++) //1≤a≤b≤n{
sum = a*a + b*b; //a^2 + b^2 = c^2
c = sqrt(sum);
if (c * c == sum && b<=c && c<=n) //1≤a≤b≤c≤n 검사{
count++;
cout<<endl<<"a :"<<a<<" b :"<<b<<" c :"<<c; //트리플렛 출력
}
}
}
return count;
}
int main(){
int N = 15;
cout <<endl<< "Number of triplets : "<<countTriplets(N);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
a :3 b :4 c :5 a :5 b :12 c :13 a :6 b :8 c :10 a :9 b :12 c :15 Number of triplets : 4
N = 15일 때 (3, 4, 5), (5, 12, 13), (6, 8, 10), (9, 12, 15)의 네 개 트리플렛이 조건을 만족함을 확인할 수 있습니다.