[백준(baekjoon) 2875] 대회 or 인턴

문제

백준 2875

N(1…100)명의 여자, M(1…100)명의 남자, 제외해야할 K(0…M+N)명이 주어질 때,
대회에 나가는 팀의 구성은 반드시 2명의 여자 + 1명의 남자가 되어야 한다.
이때, 대회에 나갈 수 있는 최대의 팀 수를 구하시오.

해결

두가지 방식으로 풀었다.

1. 단순히 if문과 연산만을 사용해 K값을 0으로 줄이는 방식
   
   1. K가 M + N보다 클 경우는 말할 필요도 없이 0이 답이다.
   2. 2 : 1비율로 M, N을 비교해 적은 값(비율 1)이 K를 고려하지 않았을 때의 팀의 수가 된다.
   3. 팀으로 확정되지 않은 나머지 사람 수를 구한다. 그리고 그 사람들을 K에서 제외한다.
   4. 그래도 K가 0이상이라면, 제외할 팀의 수를 구해 기존 확정된 팀에서 빼준다.
      제외할 팀의 수 = 팀의 단위가 3이므로 남은 사람에 + 2를 해준 후 3을 나눈 수
      (1명을 제외할 때도, 3명을 제외할 때도 1팀을 빼야한다. 그러므로 + 2를 해준다.)
2. K값을 그대로 두고 N, M을 비율대로 줄여나가 구하는 방식
   
   • 아래 세가지 조건을 만족할 때 까지, 한 팀 = 여자 두명 & 남자 한명씩 일일이 구한다.
     
     1. M >= 2 : 여자가 2명 이상이다.
     2. N >= 1 : 남자가 1명 이상이다.
     3. M + N >= 3 + K : 남은 사람들의 수가 제외할 사람들의 수 + 한 팀 이상이다.

알고리즘

그리디 알고리즘을 사용해 해결하였다.

그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요!

구현 java

1) 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int m = sc.nextInt();
9.        int k = sc.nextInt();
10.
11.        int team = 0;
12.        if (n + m > k) {
13.            team = n / 2 < m ? n / 2 : m;
14.            k -= (n + m) - team * 3; // rest 제외
15.            if (k > 0) team -= (k + 2) / 3;
16.        }
17.        System.out.println(team);
18.    }
19.}

2) 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int m = sc.nextInt();
9.        int k = sc.nextInt();
10.
11.        int team = 0;
12.        while (n >= 2 && m >= 1 && n + m >= 3 + k) {
13.            n -= 2;
14.            m--;
15.            team++;
16.        }
17.        System.out.println(team);
18.    }
19.}

결과

1. 단순히 if문과 연산만을 사용해 K값을 0으로 줄이는 방식
2. K값을 그대로 두고 N, M을 비율대로 줄여나가 구하는 방식

조건을 만족할 때까지 while문을 도는게 (2번) 단순히 연산을 사용한 방식 (1번) 보다 느릴줄 알았는데,
데이터 조건이 작아서 그런지 시간이 똑같다..