[백준/알고리즘] 2875번 대회 or 인턴 (브론즈 3)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 2875번

 

현재 학교에는 여학생이 N명, 남학생이 M명이 있다.
대회에는 여학생 1명과 남학생 2명이 팀을 이뤄 나아갸 한다는 조건이 있다.
하지만 학생들 중 K명의 학생은 인턴쉽에 참가해야만 하고, 이때 대회에 출전하는 최대 팀 수를 출력해야 한다.

 

풀이 알고리즘 : 그리디, 구현?

 

남학생은 2명씩 팀에 포함되기 때문에, 남학생 수가 홀수인 경우 한명이 무조건 남을것이라 생각했다.

 

그래서 남학생 수가 홀수인 경우는 남는 1명을 먼저 인턴쉽 인원에 포함하였다.

 

이후 남학생 두명으로 만들 수 있는 팀 (mteam)과 여학생 한명으로 만들 수 있는 팀 (wteam)의 수를 비교하여,

 

더 많은 개수의 팀을 더 적은 개수의 팀으로 맞춰주면서 k를 줄여주었다.

 

M, N, K 가 굉장히 작은 수여서, 시간제한에는 걸리지 않았다.

 

소스코드 보기

 

/*
    BOJ 2875 (https://www.acmicpc.net/problem/2875)
*/

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int main(void) {
    cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, k;    // 여학생의 수, 남학생의 수, 인턴쉽 참여 인원 수
    cin >> n >> m >> k;

    while(k) {
        if(n % 2 != 0) {    // 남학생이 홀수면 짝수로 맞춤
            n--;
        } else {
            int mteam = n / 2;
            int wteam = m;

            // 더 인원이 많은 팀을 적은 팀으로 맞춤
            if(mteam < wteam) {
                m--;
            } else if(1 < k) {
                n -= 2;
                k--;
            } else {
                n--;
            }
        }
        k--;
    }

    cout << min(n / 2, m) << "\n";
}