크기가 n인 배열 A가 있다고 가정해 보겠습니다. 이 배열은 n개의 학생 그룹을 나타내며, 각 그룹은 다음 두 가지 유형 중 하나입니다.
- 1인 그룹 : 누구와도 자유롭게 팀을 이룰 수 있는 학생 한 명
- 2인 그룹 : 반드시 같은 팀에서 함께 코드를 작성하고 싶어 하는 학생 두 명
멘토는 정확히 3명으로 구성된 팀을 만들어야 합니다. 우리가 구해야 할 것은 멘토가 만들 수 있는 3인 팀의 최대 개수입니다. 단, 2인 그룹의 경우 두 학생이 모두 참여하거나 모두 빠져야 하며, 참여한다면 반드시 같은 팀에 배정되어야 한다는 조건이 있습니다.
예시로 이해하기
입력이 A = [2, 2, 2, 1, 1, 1, 1]이라면 출력은 3입니다. 멘토는 다음과 같이 세 개의 팀을 구성할 수 있기 때문입니다.
- [첫 번째 2인 그룹 + 일곱 번째 1인 그룹]
- [두 번째 2인 그룹 + 여섯 번째 1인 그룹]
- [세 번째 2인 그룹 + 네 번째 1인 그룹]
접근 방법
핵심 아이디어는 매우 단순합니다. 배열을 한 번 순회하면서 1인 그룹의 개수(p)와 2인 그룹의 개수(q)를 센 후, 두 값의 크기를 비교하여 최대 팀 수를 계산합니다.
- p > q인 경우 : 모든 2인 그룹에 1인 그룹을 하나씩 배정해 q개의 팀을 만들고, 남은 1인 그룹(p − q명)끼리 3명씩 묶습니다. 답은
q + (p - q) / 3입니다. - p ≤ q인 경우 : 각 1인 그룹을 서로 다른 2인 그룹과 짝지어 최대 p개의 팀을 만들 수 있습니다. 남는 2인 그룹은 인원이 2명뿐이라 더 이상 팀을 꾸릴 수 없으므로 답은
p입니다.
풀이 단계
위 아이디어를 의사코드로 표현하면 다음과 같습니다.
p := 0
q := 0
x := 배열 A의 크기
i := 0부터 시작하여 i < x 동안 i를 1씩 증가시키며 반복:
a := A[i]
만약 a가 1과 같다면:
p := p + 1
아니면:
q := q + 1
만약 p > q라면:
return q + (p - q) / 3
그렇지 않고 p < q라면:
return p
그 외의 경우:
return p
C++ 구현 예제
실제 동작을 더 잘 이해할 수 있도록 전체 C++ 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int p = 0, q = 0;
int x = A.size();
for (int i = 0; i < x; i++){
int a = A[i];
if (a == 1){
p = p + 1;
}
else{
q = q + 1;
}
}
if (p > q){
return q + (p - q) / 3;
}
else if (p < q){
return p;
}
else{
return p;
}
}
int main(){
vector<int> A = { 2, 2, 2, 1, 1, 1, 1 };
cout << solve(A) << endl;
}
입력
{ 2, 2, 2, 1, 1, 1, 1 }
출력
3
마무리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 상수 공간으로 해결할 수 있습니다. 그룹의 유형만 파악하면 되는 단순한 카운팅 문제처럼 보이지만, 2인 그룹은 절대 분리할 수 없다는 제약 조건을 어떻게 처리하느냐가 관건이 되는 대표적인 그리디(Greedy) 연습 문제입니다.