[백준/C++] 2875번 대회 or 인턴

2023. 1. 30. 13:35C++/Greedy Alogirhm

https://www.acmicpc.net/problem/2875

 

2875번: 대회 or 인턴

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

www.acmicpc.net

 

문제

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

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

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

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

입력

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

출력

 

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

 


그리디 문제입니다. 위의 경우 팀이 만들어 질 수 있는 경우는 총 3가지입니다.

  • 인턴쉽 참가하는 인원이 없는 경우 2가지
    • 여학생의 수 / 2
    • 남학생의 수
  • 인턴쉽에 참가하는 학생이 존재하는 경우 1가지
    • (남학생의 수 + 여학생의 수 - 인턴쉽 참가하는 인원 수) / 3

위 세 가지 경우의 수 중에서 가장 최솟값을 구하는게 답이 된다.

여학생이 아무리 많아도 남학생 수가 적으면 남학생 수 기준으로 팀이 구성되고, 반대로 남학생 수 가 많아도 여학생 수의 비율이 적으면 여학생을 기준으로 팀이 완성 되기 때문이다. 그래서 작은 인원을 기준으로 팀을 구성하는 것이기 떄문에 각 경우중에서 가장 작은 값을 골라 준다.

전체 소스코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n,m,k; //n : 여학생의 수, m : 남학생의 수, k : 인턴쉬에 참여해야하는 인원
    
    cin>>n>>m>>k;
    
    cout<<min(min(n/2,m),(n+m-k)/3)<<endl;
    
    
    return 0;
}

 

'C++ > Greedy Alogirhm' 카테고리의 다른 글

[백준/C++] 11000번 강의실 배정  (0) 2023.01.31
[백준/C++] 11047번 동전 0  (0) 2023.01.30