C++로 해결하는 못생긴 수(Ugly Number) III

이번 글에서는 n번째 못생긴 수(Ugly Number)를 찾는 프로그램을 C++로 구현해 보겠습니다. 여기서 말하는 못생긴 수란 a, b 또는 c 중 하나 이상으로 나누어 떨어지는 양의 정수를 의미합니다.

예를 들어 n = 3, a = 2, b = 3, c = 5라고 가정해 보겠습니다. 이 경우 못생긴 수는 [2, 3, 4, 5, 6, 8, 9, 10] 순서로 나열되며, 세 번째 값인 4가 출력 결과가 됩니다.

문제 해결 접근 방법

이 문제는 포함-배제 원리(Inclusion-Exclusion Principle)와 이진 탐색(Binary Search)을 결합하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

x 이하의 수 중 a, b, c로 나누어 떨어지는 수의 개수를 계산하는 ok(x, a, b, c) 함수를 만듭니다. 이 함수는 포함-배제 원리에 따라 아래 값을 반환합니다.
(x/a) + (x/b) + (x/c) − (x/lcm(a,b)) − (x/lcm(b,c)) − (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))
ok(mid)의 결과가 n 이상이라면 n번째 못생긴 수는 mid 이하 범위에 존재한다는 뜻이므로, 탐색 상한을 mid로 좁혀 나갑니다.

이진 탐색 진행 과정

탐색 범위를 초기화합니다. low := 1, high := 2 × 10⁹
low < high를 만족하는 동안 반복합니다.
mid := low + (high − low) / 2 로 중간값을 계산합니다.
x := ok(mid, a, b, c) 를 호출해 mid 이하의 못생긴 수 개수를 구합니다.
x ≥ n이면 high := mid로, 그렇지 않으면 low := mid + 1로 갱신합니다.

반복이 종료되면 high가 곧 n번째 못생긴 수이므로 high를 반환하면 됩니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    lli gcd(lli a, lli b){
        return b == 0? a: gcd(b, a % b);
    }
    lli lcm(lli a, lli b){
        return a * b / gcd(a, b);
    }
    lli ok(lli x, lli a, lli b, lli c){
        return (x / a) + (x / b) + (x / c) - (x / lcm(a, b)) - (x / lcm(b, c)) - (x / lcm(a, c)) + (x / lcm(a, lcm(b, c)));
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1;
        int high = 2 * (int) 1e9;
        while(low < high){
            int mid = low + (high - low) / 2;
            int x = ok(mid, a, b, c);
            if(x>= n){
                high = mid;
            }
            else low = mid + 1;
        }
        return high;
    }
};
main(){
    Solution ob;
    cout << (ob.nthUglyNumber(3,2,3,5));
}

입력