[백준] (실패) 2875 대회 or 인턴

Hyun·2025년 7월 25일

백준

목록 보기

100/123

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

입력

첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),

출력

만들 수 있는 팀의 최대 개수을 출력하면 된다.

예제 입력 1

6 3 2

예제 출력 1

예제 입력 2

2 1 1

예제 출력 2

예제 입력 3

6 10 3

예제 출력 3

풀이(실패)

처음에 풀었던 방식은, 팀을 먼저 구성하고 남은 인원들중 K명을 인턴으로 보내는 것을 생각했다.
이렇게 되면 남은 인원들이 K명 이상인 경우, 팀을 구성한 단계에서 끝나버리기 때문에 간단하다고 생각했다.

그리고 남은 인원들이 K명 이하인 경우에는 앞서 구성한 팀에서 누군가(남자or여자)를 빼야했는데, 누구를 빼야할지 기준 설정이 어려웠다. 그래서 마지막 부분에 얼렁 뚱땅 값이 -가 나오는 경우는 0을 출력하도록 처리했는데, 이는 올바른 방법이 아니었고, 결국 해결하지 못했다.

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 대회 나갈 땐 여자 2명, 남자 1명으로 구성하는게 원칙임
# N명의 여학생과 M명의 남학생이 팀원을 찾고 있음
# 대회에 참여하려는 학생들 중 K명은 반드시 인턴십 참여해야함(대회 참여 못함)

# 최대한 대회에 참여한 팀임 많아야 함!
# 여학생 수 N, 남학생 수 M, 인턴십 필수인 수 K
# => 만들 수 있는 팀의 최대 개수를 출력

# (여학생이 부족한경우) 
# N <= 2M 이면 여학생 기준으로 팀 구성
# N/2 개의 팀 구성 가능
# 남은 남학생 수 = M - N/2, 이들 중 K명을 인턴십 보내야함
# K > M - N/2 인 경우, 나머지를 여학생에서 빼내야 함
# 이 경우 K -(M - N/2) 명을 여학생에서 빼내야함 
# 빼내게 된다면 최대 참여 팀수는 (N - (K - (M - N/2))) / 2 가 됨

# (남학생이 부족한 경우)
# N > 2M 이면 남학생 기준으로 팀 구성
# M 개의 팀 구성 가능
# 남은 여학생 수 = N - 2M, 이들 중 K명을 인턴십 보내야 함
# K > N - 2M 인 경우, 나머지를 남학생에서 빼내야 함
# 이 경우 K - (N - 2M) 명을 남학생에서 빼내야 함
# 빼내게 된다면 최대 참여 팀수는 M - (K - (N - 2M)) 이 된다

N, M, K = map(int, input().split())
ans = 0
# 여학생이 부족한 경우
if N <= 2*M :
    if K > M - N//2:
        ans = (N - (K - (M - N//2))) // 2
    else:
        ans = N//2
# 남학생이 부족한 경우
else:
    if K > N - 2*M:
        ans = M - (K - (N - 2*M))
    else:
        ans = M

if ans < 0:
    print(0)
else:
    print(ans)

이 후 타 풀이를 참고하니, 나의 풀이 방법(팀을 먼저 구성하고 남은 인원을 K명만큼 빼고, 이후 상황에 대해 대응)과 순서가 다르게 K명의 인원을 팀 구성을 고려한 적절한 방법(하위 기술)으로 인턴으로 빼고, 남은 인원들로 팀을 구성하는 방식이었다.

이 경우 인턴으로 뽑을 인원을 한명씩 뽑는데, 미래의 팀 구성을 고려하여 성비를 고려하여 비율이 초과한 성에 대해 한명씩 뽑게 되었다(K명을 뽑을 때까지)

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 팀을 먼저 꾸리는 것보다, 빼낼 인턴을 먼저 정해야 한다

N, M, K = map(int, input().split())
while K != 0:
    if N > 2*M:
        N-=1
        K=-1
    else:
        M-=1
        K-=1

if N >= 2*M:
   print(M)
else:
    print(N//2)