C++로 두 그룹의 인원으로 구성할 수 있는 최대 3인 팀 수 구하기

이 문제에서는 두 개의 정수 N과 M이 주어집니다. N은 1번 그룹의 인원 수, M은 2번 그룹의 인원 수를 의미합니다. 우리의 과제는 두 그룹의 인원으로 만들 수 있는 3인 팀의 최대 개수를 찾는 프로그램을 작성하는 것입니다.

팀을 구성할 때는 두 그룹에서 사람을 선택하여 최대한 많은 팀을 만들어야 하며, 각 팀에는 반드시 두 그룹의 사람이 각각 최소 한 명씩 포함되어야 합니다.

문제 이해를 위한 예시

입력 − N = 5, M = 3

출력 − 2

설명 −

팀은 다음과 같이 구성됩니다.

팀 1: 1번 그룹 인원 → 2명 ; 2번 그룹 인원 → 1명
1번 그룹 잔여 인원 = 3명 ; 2번 그룹 잔여 인원 = 2명
팀 2: 1번 그룹 인원 → 2명 ; 2번 그룹 인원 → 1명
1번 그룹 잔여 인원 = 1명 ; 2번 그룹 잔여 인원 = 1명
더 이상 3인 팀을 만들 수 없습니다.

해결 접근 방법

이 문제를 해결하려면, 인원이 적은 그룹에서 1명, 인원이 많은 그룹에서 2명을 선택하여 팀을 만듭니다. 팀을 구성할 때마다 각 그룹의 남은 인원 수를 갱신하고, 팀 개수를 세는 변수를 유지하면서 팀이 생성될 때마다 1씩 증가시킵니다. 이 과정을 더 이상 팀을 만들 수 없을 때까지 반복하면 됩니다.

예제 코드

두 그룹으로 구성할 수 있는 최대 3인 팀 수를 찾는 C++ 프로그램 −

#include <iostream>
using namespace std;
int CountTeams(int N, int M) {
    int teamCount = 0;
    while (N >= 1 && M >= 1 && N + M >= 3) {
        if (N > M) {
            N = N-2;
            M = M-1;
        }
        else {
            N = N-1;
            M = M-2;
        }
        teamCount++;
    }
    return teamCount;
}
int main() {
    int N = 5, M = 3;
    cout<<"만들 수 있는 최대 3인 팀 수: "<<CountTeams(N, M);
    return 0;
}

출력 결과

만들 수 있는 최대 3인 팀 수: 2

이 알고리즘은 매번 가능한 한 균형 있게 양쪽 그룹의 인원을 소모하므로, 주어진 조건(각 팀에 두 그룹의 인원이 모두 포함)을 만족하면서 팀 수를 최대화할 수 있습니다. 시간 복잡도는 팀 하나당 O(1)의 연산을 수행하므로 전체적으로 O(min(N, M))입니다.