C++로 고객 전화 시점에 맞춰 수거해야 할 최소 주문 수 계산하기

문제 설명

세 개의 숫자 n, m, z가 주어진다고 가정해 봅시다. 어떤 사무실은 n분마다 고객으로부터 전화를 받고, m분마다 배송 주문이 도착합니다. 사무실은 총 z분 동안 운영됩니다.

우리가 구해야 하는 것은, 고객이 전화를 걸어올 때 아직 처리되지 않은 주문이 남아 있지 않도록 하기 위해 최소한 몇 번의 주문을 수거해야 하는지입니다. 단, 주문을 접수하고 고객과 통화하는 데는 정확히 1분이 걸린다고 가정합니다.

예를 들어 입력이 n = 1, m = 2, z = 5라면 출력은 2가 됩니다. 2분째와 4분째에 도착하는 주문을 수거해야 하기 때문입니다.

접근 방법

이 문제는 최대공약수(GCD)와 최소공배수(LCM)의 관계를 이용하면 간단하게 해결할 수 있습니다.

n분마다 전화가 걸려오고 m분마다 주문이 도착한다면, 두 이벤트가 동시에 발생하는 지점은 n과 m의 최소공배수(LCM) 간격입니다. 따라서 전체 영업 시간 z를 LCM으로 나누면, 전화와 주문이 겹치는 횟수, 즉 수거해야 하는 최소 주문 수를 구할 수 있습니다.

최소공배수는 다음 공식으로 계산됩니다.

LCM(n, m) = (n * m) / GCD(n, m)

따라서 최종 반환값은 다음과 같습니다.

return z / ((n * m) / gcd(n, m));

C++ 구현 예제

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

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, int z){
    return z / ((n * m) / __gcd(n, m));
}

int main(){
    int n = 1;
    int m = 2;
    int z = 5;
    cout << solve(n, m, z) << endl;
}

입력

1, 2, 5

출력

2

코드 설명

__gcd(n, m) 함수는 C++ 표준 라이브러리에서 제공하는 최대공약수 계산 함수입니다. 위 예제에서 n = 1, m = 2이므로 LCM은 (1 × 2) / 1 = 2가 됩니다. 영업 시간 z = 5를 LCM인 2로 나누면 2가 되며, 이것이 곧 수거해야 하는 최소 주문 수입니다.

이 알고리즘의 시간 복잡도는 GCD 계산에 드는 O(log(min(n, m)))으로 매우 효율적이며, 큰 입력값에도 안정적으로 동작합니다.