문제 소개
변수 N, M, A, B가 주어졌을 때, 두 양의 정수로 이루어진 순서쌍 (i, j) 중에서 그 합 (i + j)이 A와 B로 모두 나누어지는 쌍의 개수를 구하는 것이 목표입니다. 이때 i와 j는 각각 1 ≤ i ≤ N, 1 ≤ j ≤ M의 범위를 가져야 합니다.
가장 직관적인 풀이 방법은 i와 j에 대해 두 개의 반복문을 사용해 가능한 모든 쌍을 탐색하는 것입니다. 각 쌍마다 (i + j) % A == 0 && (i + j) % B == 0 조건을 검사하고, 조건을 만족하면 카운트를 1씩 증가시킵니다.
구체적인 예제를 통해 살펴보겠습니다.
입력
N = 5, M = 10, A = 2, B = 3;
출력
(i+j)가 A와 B로 모두 나누어지는 순서쌍 (i, j)의 개수: 9
설명
조건을 만족하는 쌍은 (1,5), (2,4), (2,10), (3,3), (3,9), (4,2), (4,8), (5,1), (5,7)로 총 9개입니다.
입력
N = 10, M = 10, A = 10, B = 11;
출력
(i+j)가 A와 B로 모두 나누어지는 순서쌍 (i, j)의 개수: 0
설명
조건을 만족하는 쌍이 하나도 존재하지 않습니다.
알고리즘 접근 방법
정수 N, M, A, B를 입력받습니다.
함수 sumDivisible(int n, int m, int a, int b)는 네 개의 변수를 받아 합이 A와 B로 모두 나누어지는 순서쌍의 개수를 반환합니다.
쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.
두 개의 for 반복문을 사용해 i와 j의 모든 조합을 탐색합니다.
i는 1부터 n까지, j는 1부터 m까지 반복합니다.
(i + j) % a == 0 && (i + j) % b == 0 조건을 검사합니다.
조건이 참이면 count를 1 증가시킵니다.
모든 반복문이 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
count를 결과값으로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int sumDivisible(int n,int m,int a,int b){
int count = 0;
for (int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if((i+j)%a==0 && (i+j)%b==0)
{ count++; }
}
}
return count;
}
int main(){
int N = 50, M = 100, A = 5, B = 10;
cout <<"Ordered pairs (i,j) where (i+j) is divisible by both A & B: "<<sumDivisible(N,M,A,B);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Ordered pairs (i,j) where (i+j) is divisible by both A & B: 500
복잡도 분석 및 추가 팁
이 방법은 두 개의 중첩된 반복문을 사용하므로 시간 복잡도는 O(N × M)입니다. 따라서 N과 M이 작거나 중간 크기일 때 적합합니다.
만약 N과 M이 매우 크다면 최소공배수(LCM)를 활용한 수학적 접근으로 최적화할 수 있습니다. (i + j)가 A와 B로 동시에 나누어지려면 LCM(A, B)의 배수여야 한다는 성질을 이용하면, 각 i에 대해 조건을 만족하는 j의 개수를 등차수열 공식으로 바로 계산할 수 있어 시간 복잡도를 O(N)까지 줄일 수 있습니다.