Q 2875 대회 or 인턴

💡 문제 요약 및 분석

백준 대학교에서 대회를 나갈 때는 여학생 2명 + 남학생 1명이 조를 짜서 나가야 한다. 대회에 참여하려는 학생 중 K명은 인턴쉽 프로그램에 참여해야 한다. 여학생 N명, 남학생 M명, 인턴쉽에 참여해야 하는 인원 K가 주어질 때 만들 수 있는 팀의 최대 개수를 답하자. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N)

💡 알고리즘 설계

1. 남,여 학생 합쳐 K명을 제외했을 때의 경우의 수를 전부 따져보아야 한다. 만약 K==2 라면, (2,0) (1,1) (0,2) 세 가지 경우의 수가 있다. 이를 일반화하면 (K-i, i) 가 된다. 즉 이하의 반복문을 생각해볼 수 있다. for(i = 0; i <= K; i++) { 연산식 }

2. 연산식을 어떻게 구성할지 생각해보자. 남은 여학생을 2로 나누면 가능한 여학생 그룹이 몇 개인지 나오고, 남학생은 1명만 있어도 된다.

3. count 변수를 출력한다.

💡 코드

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int M = read();
        int K = read();

        int count = 0;
        for (int i = 0; i <= K; i++) {
            int female = (N - (K - i)) / 2;
            int male = M - i;
            int temp = female > male ? male : female;
            count = temp > count ? temp : count;
        }

        System.out.println(count);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(1)	O(1)