알고리즘 풀이 - 백준 2875(대회 or 인턴, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

2명의 여학생과 1명의 남학생이 팀을 결성해 대회에 나가고, K명의 인원은 반드시 인턴쉽게 참여해야할 때, 여학생 수 N, 남학생 수 M명이 있는 경우, 인턴쉽 인원을 제외하고 최대의 팀을 결성할 수 있는 수를 구하는 문제

 

 

2. 풀이

 

난이도가 매우 낮은 그리디 문제이다.

여학생은 2명씩 팀을 맺어야 하니 최대로 팀을 맺을 수 있는 여학생의 경우는 n/2 팀이 가능하다.

남자는 1명씩이므로 최대 m개의 팀이 가능하다.

 

이 중 더 작은 수로 팀을 우선 결성 시킨 뒤, 남는 여자/남자의 인원 수를 합하여 인턴쉽에 보내야 하는 인원에서 제한다.

 

그리고 1개 팀은 3명이 구성되어 있으니, k가 0보다 큰 동안 1개팀씩 빼고 k를 3씩 빼서 결성 가능한 결과를 구하면 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 여학생, 남학생, 인턴쉽 참여 인원을 입력한다.
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        // 우선 최대의 팀 결성 가능 수는 n/2, m중 더 작은 수이다.
        int team = n/2 >= m ? m : n/2;
        
        // 남은 여학생 및 남학생의 수를 k에서 뺀다.
        n = n - team*2 > 0 ? n - team*2 : 0;
        m = m - team > 0 ? m - team : 0;
        k -= (n + m);
        
        // k가 0보다 크다면 인턴쉽 보낼 인원이 있다는 뜻이며, 팀 1개를 뺄 때마다 3명씩 빼면 되므로
        // k가 0보다 큰 동안 아래를 반복한다.
        while(k > 0){
            team--;
            k -= 3;
        }
        System.out.println(team);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.