[Algorithm] Greedy 대회or인턴 (백준) - 에이젠

https://www.acmicpc.net/problem/2875

2875번: 대회 or 인턴

실수

 남자1명 여자2명인데 반대로 읽음...

낙오자 계산할때 팀매칭된 그룹 수를 갱신해 주지 않아서 틀림.

공략

 

알고리즘 중급 1/3 의 그리디 연습 문제입니다.

남자가 인원수가 훨씬 많다는 가정하에 과정을 설명해보겠습니다.

1. 각각 주어진 남 여 인원수를 팀에 필요한 인원수로 나눕니다. 

    M / 2 : 몫1 + 나머지1 , N / 1 : 몫2 + 나머지2

 

2. 각각 나눈 몫중에 작은 값이 인턴이 없을 때 나올 수 있는 팀 개수입니다.

남자가 훨씬 많으니 몫2가 현재 선발 가능한 팀 개수입니다.

    인턴 선발 전 팀 개수 : 몫2  < 몫1

 

3. 팀매칭이 안된 인원수는 남자가 훨씬 많으므로 남자만 남아있는 상태입니다.

    남은 인원 : (몫2 - 몫1) * 2  + 나머지1 + 나머지2 = 낙오자

 

4. 남은 인원이 K보다 크다면 몫2가 답.

 

5. 작다면 부족한만큼 팀을 해체함

(K - 낙오자) / 3 + 나머지 

 

import java.util.*;

public class Main {

  static Scanner sc = new Scanner(System.in);
  static int N; // 여자 6
  static int M; // 남자 3
  static int K; // 인턴 2
  // 대회 팀은 남자 2명 여자 1명

  static void input() {
    N = sc.nextInt();
    M = sc.nextInt();
    K = sc.nextInt();
  }

  static void findAns() {
    int groupW = N / 2; // 6
    int groupM = M; // 1
    int restW = N % 2; // 1

    // 선발 전 가능한 팀개수
    int possibleTeam = 0;
    if (groupM > groupW) {
      possibleTeam = groupW;
    } else {
      possibleTeam = groupM; // 1
    }

    // 낙오자 수
    int straggler = 0;
    if (groupM > groupW) {
      straggler = groupM - groupW;
    } else if (groupM < groupW) {
      straggler = (groupW - groupM) * 2 + restW; // 남자 솔로 + 남은 여자들
    } else {
      straggler = restW;
    }

    // 이때 낙오자수가 K보다 같거나 크다면 현재 팀 개수가 정답
    if (straggler >= K) {
      System.out.println(possibleTeam);
      return;
    } else if (straggler < K) {// 낙오자 수가 인턴 K인원수보다 부족하다면 팀을 해체시킴

      int lackOfMember = K - straggler; // 부족한 인원수
      int rest = lackOfMember % 3 == 0 ? 0 : 1;
      int bombTeam = lackOfMember / 3 + rest;
      possibleTeam = possibleTeam - bombTeam;
      System.out.println(possibleTeam);

    }

  }

  public static void main(String[] args) {
    input();
    findAns();

  }

}

 

훨씬 간단한 풀이

https://log-laboratory.tistory.com/85

[백준] 2875번 자바 대회 or 인턴