백준 2875번 대회 or 인턴 [Greedy] :: 마이구미

이번 글은 백준 알고리즘 2875번 "대회 or 인턴" 을 다뤄본다.

이 문제는 그리디 알고리즘으로 문제를 접근할 수 있다.

그리디 알고리즘 - http://mygumi.tistory.com/121

2875번 대회 or 인턴 - https://www.acmicpc.net/problem/2875

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

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.

그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

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

문제는 팀을 구해야하는데 K명을 뺀 상태에서 최대의 팀 수를 구하는 문제이다.

한명을 뺄 때마다 여자 or 남자 어느 쪽을 빼는 것이 최선일지 알아야한다.

여자는 2명과 남자는 1명을 이루어져야 조가 만들어진다.

팀을 이루기 위해서는 1명으로 팀을 이룰수 있는 남자 쪽이 유리하기에 여자를 빼는 먼저 빼는 선택을 한다.

그 이유는 잘 생각해보면, 여자는 2명을 빼야 하나의 조가 사라지고, 남자가 1명을 빼면 사라진다.

공대에서 남자 비율이 많고, 여자 비율이 적음으로써, 여자는 아껴진다.

여기서도 똑같다. 남자 쪽이 더 아낀다고 보면 된다. (성별이 다를 뿐이다)

한명한명 뺄때마다 우리의 선택은 여자를 빼는 선택을 하면 된다.

수많은 경우가 있으니 무작정 여자를 빼면 안된다.

예를 들어보자.

위와 같은 경우가 존재하기 때문에 무작정 여자를 뺄 수 없다.

그리디 알고리즘은 그때그때 최선이라고 생각하는 것을 선택한다.

하지만, 결국 문제의 최종 결과는 최적이여야한다.

조건을 통해 최선의 선택이 최적으로 만들어주어야한다.

여자와 남자를 각각 팀을 이룰 수 있는 경우를 살펴본다.

여자는 n/2, 남자는 n으로 팀을 이룰 수 있다.

바로 이것을 기준으로 잡는 것이다.

public static int getCount(int n, boolean female) {

    if (female) {
        n = n / 2;
    }

    return n;
}

주어진 입력이 N - 10, M - 6, K - 1 경우를 보자.

여자 10/2 = 5, 남자 6인 것을 확인할 수 있다.

남자가 더 크니 남자를 빼주면 된다.

N - 10, M - 5, K - 1일 경우는 여자가 5, 남자가 5일 경우는 누굴 먼저 하는가?

이런 경우 위에서 최선의 선택으로 정의한 여자를 먼저 빼는 것이다.

남자를 빼든 여자를 빼든 팀은 4팀으로 똑같은 걸 알 수 있다.

하지만 5 2 1과 같은 경우 문제가 발생한다.

while (k-- > 0) {

    if (getCount(n, true) >= getCount(m, false)) {
        n--;
    } else {
        m--;
    }

}

k의 수만큼 하나하나 빼는 과정을 볼 수 있다.

마지막으로 n과 m이 서로 차이가 심하게 주어질 경우를 위해 아래 조건을 준다.

n/2 <= m ? n/2 : m;

그리디 알고리즘을 좀 더 와닿을 수 있는 문제라서 다루게 되었다.

전체 소스는 아래 Github URL을 통해 확인하길바란다.

백준 알고리즘 2875번 대회 or 인턴 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/Greedy/2875.java