개요
백준 문제 2875번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 90분
https://www.acmicpc.net/problem/2875
문제
백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)
백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.
백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.
여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
using namespace std;
int man,woman,objIntern;
int minTeam = 0;
void greedy()
{
int intern = 0;
while(objIntern != intern)
{
//여자 한명 빼도 팀 충족
if((woman-1)/2 >= minTeam)
{
woman--;
intern++;
}
//남자 한명 빼도 팀 충족
else if(man > minTeam)
{
man--;
intern++;
}
else if(woman/2 > man)
{
//여자뺀다
woman--;
intern++;
minTeam--;
}
else
{
man--;
intern++;
minTeam--;
}
}
cout << minTeam;
}
void solve()
{
cin >> woman >> man >> objIntern;
minTeam = min(man,woman/2);
greedy();
}
int main()
{
solve();
}
|
풀이
- 팀이 충족하는 한 남자나 여자를 빼는 것이 제일 큰 우선순위
- 팀이 충족하지 않는 경우에는 둘 중에 뺄 사람을 골라야함 -> 최대한 팀이 깨지지 않게 (woman/2 > man)
배울 점, 메모