2875_대회 or 인턴_그리디 알고리즘

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

2875번: 대회 or 인턴

문제

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

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

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

입력

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

출력

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

---

문제 이해

  N명의 여학생과 M명의 남학생 그리고 K명의 인턴쉽에서 2W 1M의 팀의 조건으로 최대의 팀을 만드는 것이 문제이다.

문제 해결

K == 0인 경우를 생각한다.

  이 경우 남학생이 여학생보다 많다면 여학생 / 2가 최대 팀이 될 것이다. 만일 여학생이 남학생 * 2 보다 많다면 남학생의 숫자가 최대 팀이 될 것이다.

 

K > 0 보다 큰 경우를 상상하자.

  1. 남학생이 여학생 / 2 보다 많은 경우, 남학생을 -1과 인턴쉽을 -1 해주고 최대 팀 갯수는 여학생 / 2로 하면 된다.

  2. 여학생이 남학생 * 2 많은 경우, 여학생을 -1과 인턴쉽을 -1 해주고 최대 팀 갯수는 남학생의 숫자로 하면된다.

  3. 그 외 경우, 인턴쉽을 -3만큼 해주면 된다. -3을 해주는 이유는 -1, -2를 해봤자 팀의 갯수는 변화가 없다. 그러므로 -3을 해주어 한팀의 인원을 빼주는 것이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int woman, man, intern;
int res;

int main(void) {
	scanf("%d %d %d", &woman, &man, &intern);

	if(woman >= man * 2)
		res = man;
	else if(woman < man * 2)
		res = woman / 2;
	while(intern > 0) {
		if(man > woman / 2) {
			man -= 1;
			intern -= 1;
			res = woman / 2;
		}
		else if(woman > man * 2) {
			woman -= 1;
			intern -= 1;
			res = man;
		}
		else {
			intern -= 3;
			man--;
			woman -= 2;
			res = man;
		}
		// cout << woman << " " << man << " " << intern << " ";
	}

	printf("%d\n", res);
	return 0;
}