[알고리즘 문제] 백준2875 - 대회or인턴

이 문제는 여학생,남학생들로 만들 수 있는 팀의 최대값을 구하는 문제이다. 팀을 만드는데 조건은 다음과 같다.

 

1. 팀의 구성원은 여학생2명, 남학생1명이다.

2. 학생들 중 k명은 반드시 인턴쉽 프로그램에 참여해야 한다.

3. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

 

 

이번 문제는 그리디알고리즘을 사용했는데, 아이디어는 다음과 같다.

 

1. 현재 학생들로 만들 수 있는 최대팀을 구한다.

2. 남은 학생들이 인턴쉽에 참여하는 학생들을 만족하는지 검사한다.

3. 만족하면 현재 팀의 개수를 출력하고, 그렇지 않으면 팀의 개수를 줄이면서 그 만큼의 학생수를 충원하면서 인턴쉽에 참여하는 학생들의 수를 만족할 때 까지 반복한다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m, k;

        n = sc.nextInt(); // 여학생 수
        m = sc.nextInt(); // 남학생 수
        k = sc.nextInt(); // 인턴팀에 참여하는 학생

        int teamCount = 0;
        int internTeam = 0;

        int man = m;
        int girl = n;

        while (girl >= 2 && man >= 1) { // 처음에 학생들로 만들 수 있는 최대의 팀을 계산

            man -= 1;
            girl -= 2;
            teamCount++;
        }

        if (man >= k || girl >= k || (man + girl) >= k) { // 남아있는 학생들이 인턴에 참여하는 학생보다 많은가 ?
            System.out.println(teamCount);
            return;

        }
        teamCount--; // 부족하면 기존의 팀에서 학생들을 뺌
        man += 1;
        girl += 2;

        while (man + girl < k) { // 기존의 팀에서 뺀 학생들의 합이 인턴에 참여하는 학생을 만족할때까지 반복
            teamCount--;
            man += 1;
            girl += 2;
        }

        System.out.println(teamCount);
    }
}

먼저 첫번쨰 while문에서 최대팀의 수를 구한다. 그리고 다음 If문에서 남은 여학생의 수,남학생의 수,남여학생의 수가 인턴쉽에 참여하는 학생수를 만족한다면 현재 팀의 수를 출력하고 종료한다.

 하지만 남아있는 학생들의 수가 인턴쉽에 참여하는 학생들의 수보다 작다면, 기존의 팀에서 학생들을 빼야한다. 두번째 while문을 이 부분에 대한 로직으로 남,여학생들의 수가 k보다 작을떄까지 반복한다(부족하면 계속 빼와야 하니깐)