[C++] BAEKJOON 2875 대회 or 인턴

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

2875번: 대회 or 인턴

그리디 알고리즘 을 이용해서 문제를 두 가지 방법으로 해결하였습니다.

1. O(K)

   남녀의 인원 수를 비교하며 팀의 개수를 최대로 할 수 있는 최상의 인원을 맞추기 위해 한 명씩 빼주었습니다.

   #include <iostream>
   
   using namespace std;
   
   int main(int argc, const char * argv[]) {
       int N,M,K;
       cin >> N >> M >> K;
       // 2명의 여학생과 1명의 남학생이 팀
       
       for (int i=0;i<K;i++){
           if (N/2 >= M){
               N--;
           }
           else M--;
       }
       
       int teamNum;
       teamNum = min(N/2, M);
       cout << teamNum << "\n";
       return 0;
   }
   

    

2. O(1)

   총 3가지 경우를 비교해줍니다.

   • N 과 M 의 수가 큰 차이가 없을 때

     (N+M-K)/3

   • N 이 M 보다 많이 클 때

     M

   • N이 M 보다 많이 작을 때

     N/2

   #include <iostream>
   
   using namespace std;
   
   int min3(int a, int b, int c){
       return min(min(a,b),c);
   }
   
   int main(){
       int N,M,K;
       cin >> N >> M >> K;
       
       cout << min3((N+M-K)/3, N/2, M) << "\n";
       
   }