[백준] 대회 or 인턴 (그리디 알고리즘, Java)

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 여자 N명, 남자 M명, 그리고 인턴쉽을 위한 인원 K명이 주어지고, 가능한 그 조건을 만족하는 팀을 많이 만드는 문제입니다.

 

저는 반복문을 이용한 그리디 알고리즘을 사용했습니다.

 

그리디 알고리즘의 설명은 아래의 포스팅에서 확인가능합니다.

 

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

 

그리디 알고리즘은 전체적인 최적화를 목표로 하지만, 각 단계에서 지역적인 최적화(현재 상태에서 가능한 최선의 선택 == Greedy)를 하는 알고리즘입니다. 따라서 이 문제에서는 최대한 팀을 많이 만들기 위한 방법이므로 그리디 알고리즘을 적용할 수 있습니다.

 

그리디 알고리즘을 적용할 수 있는지 확인하기 위해서는 최적해를 구해야합니다.

 

이번 문제에서는 매번 여자 2명, 남자 1명을 차감하면서 팀을 구성하는 것이 최선의 선택입니다.

 

---

풀이 설명을 하자면 StringTokenizer로 입력값을 공백을 기준으로 N,M,K를 구분해줍니다. 그리고 while 반복문을 사용하여 아래의 조건을 만족하는 동안 반복적으로 팀을 만듭니다.

 

• N >= 2: 여자 2명이 있어야 팀을 만들 수 있습니다.
• M >= 1: 남자 1명이 있어야 팀을 만들 수 있습니다.
• (N + M) - K >= 3: 팀을 만들기 위한 총 인원이 3명 이상이어야 합니다. (여자 2명, 남자 1명)

반복문이 한 번 실행될 때마다 팀을 하나씩 구성하고, 팀에 포함된 여자 2명과 남자 1명을 차감하여 최적해를 찾아갑니다.

---

반복문 동작 과정

1. 초기 값:
   N = 6, M = 3, K = 2
   • (N + M) - K = (6 + 3) - 2 = 7 (총 사람 수에서 인턴을 뺀 후 남은 인원)
   • N >= 2 (여자는 2명 이상), M >= 1 (남자는 1명 이상), (N + M) - K >= 3 (남은 인원 수가 3명 이상) 조건을 만족하므로 반복문을 한 번 실행합니다.
2. 첫 번째 반복:
   • N = 6, M = 3에서 2명의 여자를 차감하고 1명의 남자를 차감합니다.
   • N -= 2 → N = 4, M -= 1 → M = 2
   • cnt++ → cnt = 1 (한 팀이 결성되었습니다.)
3. 두 번째 반복:
   • (N + M) - K = (4 + 2) - 2 = 4로 남은 사람 수가 4명입니다.
   • N >= 2 (여자는 2명 이상), M >= 1 (남자는 1명 이상), (N + M) - K >= 3 (남은 인원 수가 3명 이상) 조건을 다시 만족하므로, 반복문을 한 번 더 실행합니다.
4. 두 번째 반복 후:
   • N = 4, M = 2에서 2명의 여자를 차감하고 1명의 남자를 차감합니다.
   • N -= 2 → N = 2, M -= 1 → M = 1
   • cnt++ → cnt = 2 (두 번째 팀이 결성되었습니다.)
5. 세 번째 반복:
   • (N + M) - K = (2 + 1) - 2 = 1로 남은 사람 수가 1명입니다.
   • N >= 2 (여자는 2명 이상), M >= 1 (남자는 1명 이상), (N + M) - K >= 3 (남은 인원 수가 3명 이상) 조건을 만족하지 않으므로, 반복문을 종료합니다.