[알고연] (3주차-2) 158B. Taxi

158B. Taxi

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

자동차를 최소화 한다는건 최대한 많은 사람을 한 택시에 태우는 것과 같다. (즉, 이 과정이 그리디)

1. 4명인 그룹은 통째로 다 태운다.
2. 3명인 그룹은 전부 태우고, 여기에 1명인 그룹은 무조건 같이 태운다. 1명인 그룹이 없을 경우 3명만 태운다.
3. 2명인 그룹은 두 그룹씩 같이 태운다.
4. 만약 2명인 그룹이 하나 남았을 경우, 1명인 그룹을 최대 2그룹까지 같이 태운다.
5. 1명인 그룹은 4그룹씩 같이 태운다.
6. 만약 1명인 그룹이 4그룹 미만으로 남았을 경우, 그 그룹을 다같이 태운다.

#include <bits/stdc++.h>
 
using namespace std;
int main() {
	int c4, c3, c2, c1, n, cnt;
	c4 = c3 = c2 = c1 = 0;
	cin >> n;
	while (n > 0){
		int x;
		cin >> x;
		if (x == 1) c1++;
		else if (x == 2) c2++;
		else if (x == 3) c3++;
		else c4++;
		n--;
	}
    // 과정 (1)
	cnt = c4; 
    
    // 과정 (2)
	cnt += c3; c1 -= min(c3, c1); 
    
    // 과정 (3)
	cnt += c2 / 2;
	c2 -= (c2 / 2) * 2; 
    
    // 과정 (4)
	if (c2 == 1) { 
		cnt++; c1 -= min(2, c1);
	}
    
    // 과정 (5)
	cnt += c1 / 4; c1 -= (c1 / 4) * 4; 
    
    // 과정 (6)
	if (c1 > 0) cnt++; 
    
	cout << cnt << "\n";
	return 0;
}