C++로 곱이 N보다 작은 순서쌍의 개수 구하기

하나의 수 N이 주어졌을 때, 두 양의 정수로 이루어진 순서쌍(ordered pair) 중에서 곱이 N보다 작은 쌍의 개수를 구하는 것이 목표입니다.

가장 직관적인 방법은 i를 1부터 N 미만까지, j를 1부터 (i*j)가 N 미만일 때까지 반복하면서 조건을 만족할 때마다 카운트를 1씩 증가시키는 것입니다.

예제를 통해 자세히 살펴보겠습니다.

입력 예시 1

N=4

출력 결과 1

곱이 N보다 작은 순서쌍의 개수: 5

설명: 조건을 만족하는 쌍은 (1,1), (1,2), (1,3), (2,1), (3,1)로 총 5개입니다.

입력 예시 2

N=100

출력 결과 2

곱이 N보다 작은 순서쌍의 개수: 473

설명: (1,1), (1,2), (1,3)부터 (97,1), (98,1), (99,1)까지 모두 포함하면 총 473개입니다.

풀이 접근 방식

• 정수 N을 입력받습니다.

• productN(int n) 함수는 n을 매개변수로 받아 곱이 n보다 작은 순서쌍의 개수를 반환합니다.

• 쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.

• 두 개의 중첩된 for 루프를 사용하여 가능한 모든 쌍을 탐색합니다.

• 바깥쪽 루프는 i=1부터 i<n까지, 안쪽 루프는 j=1부터 (i*j)<n까지 반복합니다.

• 조건을 만족할 때마다 count를 1씩 증가시킵니다.

• 모든 루프가 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.

• count를 결과값으로 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int productN(int n){
   int count = 0;
   for (int i = 1; i < n; i++){
      for(int j = 1; (i*j) < n; j++)
         { count++; }
   }
   return count;
}
int main(){
   int N = 6;
   cout <<"곱이 N보다 작은 순서쌍의 개수:"<<productN(N);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.

곱이 N보다 작은 순서쌍의 개수: 10

N=6인 경우 조건을 만족하는 쌍은 (1,1), (1,2), (1,3), (1,4), (1,5), (2,1), (2,2), (3,1), (4,1), (5,1)로 총 10개입니다.