문제 이해하기
이 문제에서는 'start', 'end', 'number'라는 세 개의 입력 변수가 주어집니다. 목표는 start부터 end까지 범위 내에 있는 자연수 쌍 중에서 최대공약수(GCD)가 'number'와 정확히 일치하는 쌍의 개수를 찾는 것입니다. 다시 말해, GCD(A, B) = number이면서 A와 B가 모두 [start, end] 범위에 속하는 경우를 세면 됩니다.
예제를 통해 자세히 살펴보겠습니다.
입력: start=5, end=20, number=8
출력: GCD가 주어진 숫자와 같은 자연수 쌍의 개수: 3
설명: 5부터 20 사이에서 GCD가 8인 쌍은 (8, 8), (8, 16), (16, 8)입니다.
입력: start=20, end=30, number=7
출력: GCD가 주어진 숫자와 같은 자연수 쌍의 개수: 2
설명: 20부터 30 사이에서 GCD가 7인 쌍은 (21, 28), (28, 21)입니다.
접근 방법 1: 완전 탐색 (브루트 포스)
가장 직관적인 방법은 두 개의 중첩 반복문을 사용하여 가능한 모든 쌍 (i, j)을 확인하는 것입니다. 바깥쪽 반복문은 i를 start부터 end까지, 안쪽 반복문은 j를 start부터 end까지 순회하며, 각 쌍에 대해 GCD(i, j)가 number와 같은지 검사합니다.
start, end, number를 정수형 변수로 받습니다.
GCD(int a, int b) 함수는 재귀적으로 동작하며, 인자로 받은 a와 b의 최대공약수를 반환합니다.
b가 0이 아니면 GCD(b, a % b) 형태로 자기 자신을 재귀 호출하고, b가 0이면 a를 반환합니다. 이는 유클리드 호제법을 활용한 구현입니다.
GCD_pairs(int start, int end, int number) 함수는 경계값 start, end와 목표 GCD인 number를 받아 조건을 만족하는 쌍의 개수를 반환합니다.
count 변수를 0으로 초기화합니다.
두 개의 반복문으로 쌍의 각 원소를 순회합니다. 바깥쪽 반복문은 i를 start부터 end까지, 안쪽 반복문은 j를 start부터 end까지 진행합니다.
각 쌍 (i, j)에 대해 GCD(i, j) == number인지 확인하고, 참이면 count를 1 증가시킵니다.
모든 탐색이 끝나면 count에는 GCD가 number인 쌍의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
이 방법의 시간 복잡도는 대략 O((end − start + 1)2)이며, 여기에 각 GCD 계산에 드는 로그 시간이 추가됩니다. 따라서 범위가 넓어지면 성능이 급격히 저하될 수 있습니다.
접근 방법 2: 효율적인 접근 (범위 축소)
GCD(i, j)가 number가 되려면 i와 j가 반드시 number로 나누어떨어져야 합니다. 따라서 범위 전체를 탐색할 필요 없이 number의 배수만 살펴보면 되며, 그 개수는 최대 (end − start) / number개입니다.
핵심 아이디어는 start와 end를 다음과 같이 변환하는 것입니다.
start = (start + number − 1) / number → 올림 나눗셈으로, 범위 내 첫 번째 number의 배수를 나타내는 몫을 구합니다.
end = end / number → 내림 나눗셈으로, 범위 내 마지막 number의 배수를 나타내는 몫을 구합니다.
이렇게 변환하면 원래 범위의 number 배수들이 1부터 새로운 end까지의 연속된 정수로 매핑됩니다. 변환된 범위에서 GCD(i, j) == 1인 쌍의 개수를 세면 그것이 곧 원래 범위에서 GCD가 number인 쌍의 개수와 같습니다. 그 이유는 GCD(k×number, m×number) = number × GCD(k, m)이라는 성질 때문입니다.
start, end, number를 정수형 변수로 받습니다.
start = (start + number − 1) / number, end = end / number로 값을 갱신합니다.
GCD(int a, int b) 함수는 재귀적으로 동작하며, 인자로 받은 a와 b의 최대공약수를 반환합니다.
b가 0이 아니면 GCD(b, a % b) 형태로 재귀 호출하고, b가 0이면 a를 반환합니다.
GCD_pairs(int start, int end, int number) 함수는 축소된 범위에서 서로소(coprime)인 쌍의 개수를 반환합니다.
count 변수를 0으로 초기화합니다.
두 개의 반복문으로 쌍의 각 원소를 순회합니다.
각 쌍 (i, j)에 대해 GCD(i, j) == 1인지 확인하고, 참이면 count를 1 증가시킵니다.
탐색이 끝나면 count가 곧 GCD가 number인 쌍의 총 개수입니다.
count를 결과로 반환합니다.
예제 코드 (완전 탐색)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == number){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
cout << "GCD가 주어진 숫자와 같은 자연수 쌍의 개수: " << GCD_pairs(start, end, number) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
GCD가 주어진 숫자와 같은 자연수 쌍의 개수: 7
예제 코드 (효율적인 접근)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == 1){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
start = (start + number - 1) / number;
end = end / number;
cout << "GCD가 주어진 숫자와 같은 자연수 쌍의 개수: " << GCD_pairs(start, end, number) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
GCD가 주어진 숫자와 같은 자연수 쌍의 개수: 7
마무리
두 방식 모두 동일한 결과를 출력하지만, 효율적인 접근 방식은 탐색 범위를 number배 축소하므로 범위가 넓거나 number가 클 때 특히 유리합니다. 예제에서 start=10, end=30, number=10인 경우, number의 배수는 10, 20, 30 세 개뿐이므로 실제로는 {1, 2, 3} 범위에서 서로소인 쌍만 확인하면 되어 연산량이 크게 줄어듭니다.