문제 개요
하나의 숫자 N이 주어졌을 때, 1부터 N 사이의 숫자들 중에서 두 수의 곱이 두 수의 합으로 나누어떨어지는 쌍의 개수를 구하는 것이 목표입니다.
예시를 통해 자세히 살펴보겠습니다.
입력 − N=11
출력 − 곱이 합으로 나누어떨어지는 쌍의 개수: 1
설명 − 숫자 3과 6의 곱은 18이고, 두 수의 합은 9입니다. 9는 18을 나머지 없이 완전히 나눌 수 있습니다.
입력 − N=30
출력 − 곱이 합으로 나누어떨어지는 쌍의 개수: 12
설명 − 조건을 만족하는 쌍은 다음과 같습니다.
(3, 6), (4, 12), (5, 20), (6, 12), (6, 30), (8, 24), (9, 18), (10, 15), (12, 24), (15, 30), (20, 30), (21, 28)
총 쌍의 개수 − 12개
접근 방식
이 문제는 FOR 루프를 두 번 중첩하여 1부터 N까지 모든 숫자 쌍을 탐색하는 방식으로 해결할 수 있습니다. 각 i에 대해 곱 (i × j)이 합 (i + j)으로 나누어떨어지는 j를 찾고, i와 j가 서로 다른 경우에 한해 카운트를 증가시킵니다.
숫자 N을 입력받습니다.
함수 Sum_N(N)은 N을 전달받아 조건을 만족하는 쌍의 개수를 반환합니다.
카운트 변수를 0으로 초기화합니다.
바깥 루프는 i = 1부터 i < N까지 순회합니다.
안쪽 루프는 j = i + 1부터 j <= N까지 순회하여 중복된 쌍과 같은 수끼리의 조합을 피합니다.
각 i와 j에 대해 temp = (i × j) % (i + j)를 계산합니다.
temp가 0이라면 합이 곱을 완전히 나눈다는 의미이므로 카운트를 1 증가시킵니다.
모든 반복이 종료되면 카운트에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
카운트를 결과값으로 반환합니다.
이 알고리즘의 시간 복잡도는 두 루프가 모두 N에 비례하여 실행되므로 O(N²)이며, 추가 공간 없이 상수 크기의 변수만 사용하므로 공간 복잡도는 O(1)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int Sum_N(int N){
int count = 0;
for (int i = 1; i < N; i++){
for (int j = i + 1; j <= N; j++){
int temp = (j * i) % (j + i);
if (!temp){
count++;
}
}
}
return count;
}
int main(){
int N = 20;
cout << "1부터 " << N << "까지의 숫자 쌍 중 곱이 합으로 나누어떨어지는 쌍의 개수: " << Sum_N(N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
1부터 20까지의 숫자 쌍 중 곱이 합으로 나누어떨어지는 쌍의 개수: 6
N이 커질수록 탐색해야 할 쌍의 수가 급격히 늘어나므로, 매우 큰 N에 대해서는 더 효율적인 수학적 접근이 필요할 수 있습니다. 하지만 위의 브루트포스 방식은 로직이 단순하고 명확하여 문제의 원리를 이해하기에 가장 좋은 출발점입니다.