C++로 A 또는 B로 나누어 떨어지는 N번째 항 찾기

이 문제에서는 세 개의 숫자 A, B, N이 주어지며, C++을 이용해 A 또는 B로 나누어 떨어지는 수열의 N번째 항을 구하는 프로그램을 작성해야 합니다.

문제 설명

A 또는 B로 나누어 떨어지는 수들을 차례대로 나열했을 때, 그중 N번째에 해당하는 값을 찾는 것이 목표입니다. 즉, A나 B로 나누어 떨어지는 수를 1번째부터 순서대로 세어 나가다가 정확히 N번째가 되는 수를 출력하면 됩니다.

예제로 이해하기

입력

A = 4, B = 3, N = 5

출력

9

설명

3 또는 4로 나누어 떨어지는 수들을 순서대로 나열하면 다음과 같습니다.

3, 4, 6, 8, 9, 12, ...

이 수열에서 5번째 항은 9입니다.

풀이 방법 1: 단순 반복문 활용

가장 직관적인 방법은 1부터 시작하는 자연수를 하나씩 검사하면서 A 또는 B로 나누어 떨어지는 수의 개수를 세는 것입니다. 개수가 N에 도달하는 순간의 수가 곧 정답이 됩니다.

예제 코드

#include<iostream>
using namespace std;
int findNTerm(int N, int A, int B) {
    int count = 0;
    int num = 1;
    while( count < N){
        if(num%A == 0 || num%B == 0)
            count++;
        if(count == N)
            return num;
        num++;
    }
    return 0;
}
int main(){
    int N = 12, A = 3, B = 4;
    cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B)<<endl;
}

출력

12th term divisible by 3 or 4 is 24

풀이 방법 2: 이진 탐색(Binary Search) 활용

N의 값이 매우 클 경우 위 방법은 비효율적일 수 있습니다. 이때는 이진 탐색을 활용하면 시간 복잡도를 크게 줄일 수 있습니다.

핵심 아이디어는 특정 값 maxNum 이하에서 A 또는 B로 나누어 떨어지는 수의 개수를 다음 공식으로 구할 수 있다는 점입니다.

개수 = maxNum/A + maxNum/B − maxNum/lcm(A,B)

여기서 lcm(A, B)은 A와 B의 최소공배수입니다. maxNum/LCM을 빼는 이유는 A와 B의 공배수가 두 번씩 중복 계산되기 때문입니다. 이 개수와 N을 비교하여 탐색 범위를 절반씩 줄여가며 답을 찾습니다.

예제 코드

#include <iostream>
using namespace std;
int findLCM(int a, int b) {
    int LCM = a, i = 2;
    while(LCM % b != 0) {
        LCM = a*i;
        i++;
    }
    return LCM;
}
int findNTerm(int N, int A, int B) {
    int start = 1, end = (N*A*B), mid;
    int LCM = findLCM(A, B);

while (start < end) {
    mid = start + (end - start) / 2;
    if ( ((mid/A) + (mid/B) - (mid/LCM)) < N)
        start = mid + 1;
    else
        end = mid;
}
    return start;
}
int main() {
    int N = 12, A = 3, B = 4;
    cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B);
}

출력

12th term divisible by 3 or 4 is 24

정리

N이 작다면 단순 반복문으로 충분하지만, N이 커질수록 이진 탐색 기반 풀이가 훨씬 효율적입니다. 최소공배수(LCM)를 이용해 중복을 제거하고 탐색 범위를 조절하는 것이 이 문제의 핵심 포인트입니다.