문제 소개
정수 a, b, n이 주어졌을 때, 1부터 a까지의 범위에서 값 x를 선택하고 1부터 b까지의 범위에서 값 y를 선택하여 만들 수 있는 모든 쌍 (x, y) 가운데, 두 수의 합이 n으로 나누어 떨어지는 쌍의 개수를 구하는 것이 이 글의 목표입니다.
예제 1
입력 − int a = 2, b = 3, n = 2
출력 − 합이 N으로 나누어 떨어지는 쌍의 개수: 3
설명 −
먼저 1부터 a까지의 숫자는 1, 2입니다. 다음으로 1부터 b까지의 숫자는 1, 2, 3입니다. 만들 수 있는 쌍은 (1,1), (1,2), (1,3), (2,1), (2,2), (2,3)이며, 각각의 합은 2, 3, 4, 3, 4, 5입니다. 이 가운데 2, 4, 4는 주어진 N, 즉 2로 나누어 떨어지므로 개수는 3이 됩니다.
예제 2
입력 − int a = 4, b = 3, n = 3
출력 − 합이 N으로 나누어 떨어지는 쌍의 개수: 4
설명 −
먼저 1부터 a까지의 숫자는 1, 2, 3, 4입니다. 다음으로 1부터 b까지의 숫자는 1, 2, 3입니다. 만들 수 있는 쌍은 (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)이며, 각각의 합은 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7입니다. 이 가운데 3, 3, 6, 6은 주어진 N, 즉 3으로 나누어 떨어지므로 개수는 4가 됩니다.
프로그램에서 사용한 접근 방식
- 1부터 a까지, 1부터 b까지의 범위와 나눗셈 조건에 사용할 정수 변수 a, b, n을 입력받습니다.
- 이후 처리를 위해 모든 데이터를 함수에 전달합니다.
- 쌍의 개수를 저장할 임시 변수 count를 생성합니다.
- i를 1부터 a까지 반복하는 FOR 루프를 시작합니다.
- 루프 안에서 j를 1부터 b까지 반복하는 또 다른 FOR 루프를 시작합니다.
- 루프 안에서 sum을 i + j로 설정합니다.
- IF 조건으로 sum % n == 0인지 검사하고, 참이면 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count를 반환합니다.
- 결과를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
int Pair_a_b(int a, int b, int n){
int count = 0;
for (int i = 1; i <= a; i++){
for (int j = 1; j <= b; j++){
int temp = i + j;
if (temp % n == 0){
count++;
}
}
}
return count;
}
int main(){
int a = 2, b = 20, n = 4;
cout<<"1부터 a까지, 1부터 b까지의 수로 만든 쌍 중 합이 N으로 나누어 떨어지는 쌍의 개수: "<<Pair_a_b(a, b, n);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
1부터 a까지, 1부터 b까지의 수로 만든 쌍 중 합이 N으로 나누어 떨어지는 쌍의 개수: 10
복잡도 분석
이 방식은 가능한 모든 쌍을 한 번씩 확인하므로 시간 복잡도는 O(a × b)이며, 추가로 사용하는 메모리는 상수 수준(O(1))입니다. 범위가 매우 커지는 경우에는 각 숫자를 n으로 나눈 나머지별 개수를 미리 세어 두고 나머지끼리 조합하는 방식으로 최적화할 수 있습니다.