BOJ 2875 - 대회 or 인턴

문제

BOJ 2875 - 대회 or 인턴

여학생 N명, 남학생 M명이 있을 때, K명은 반드시 인턴에 참여해야 한다. 여학생 2명과 남학생 1명으로 팀을 구성할 때 최대 팀 수를 구하라.

입력

여학생 수 N, 남학생 수 M, 인턴 인원 K가 주어진다.

출력

최대 팀 수를 출력한다.

예제

풀이

그리디하게 팀을 하나씩 구성하면서, 남은 인원이 인턴 K명 이상인지를 확인한다.

1. 여학생이 2명 이상이고 남학생이 1명 이상인 동안 반복한다
2. 추가 조건으로 N + M >= K + 3 (남은 인원이 인턴 + 팀원 3명 이상)을 확인한다
3. 조건을 만족하면 여학생 2명, 남학생 1명을 소모하고 팀 수를 증가시킨다
4. 조건 불만족 시 반복을 종료하고 팀 수를 출력한다

핵심 아이디어: 팀을 구성할 때마다 남은 전체 인원이 인턴 수 이상인지를 체크하면, 최적해를 보장할 수 있다.

코드

N, M, K = map(int, input().split())
ans = 0
 
while N >= 2 and M >= 1 and N + M >= K + 3:
    N -= 2
    M -= 1
    ans += 1
print(ans)

복잡도

• 시간: O(min(N, M))
• 공간: O(1)