158-B, *1100

Problem - 158B - Codeforces

문제

• $n$개의 그룹이 있고, 각 그룹에는 $s_{i}(1\leq s_{i} \leq4)$ 명의 사람이 있다
• 모든 사람이 최대 4명이 탈 수 있는 택시로 이동을 한다.
• 같은 그룹에 있는 사람들은 같은 택시를 타야한다

필요한 택시의 최소 수?

 

O(1)

Greedy
let 편의상 $s_{i}=k$인 그룹을 $s_{k}$이라 부르자
$s_{4}$은 여석없이 하나의 택시를 탄다($s_{4}$가 없어질때까지 반복)
$s_{3}$이 먼저 택시에 타고 $s_{1}$인 그룹이 있다면 여석에 채워넣는다($s_{3}$이 없어질때까지 반복)
$s_{2}$가 먼저 택시에 타고 $s_{2}$가 남아 있다면 여석에 채워넣는다($s_{2}$가 없어질때까지 반복)
만약 $s_{2}$가 남아있지 않다면 여석을 모두 $s_{1}$로 채운다

Claim
Greedy stay ahead

$\because$
비교의 편의를 위해 Greedy와 최적해 알고리즘에서
큰 그룹이 있는 택시들은 아래쪽에 배치하고 택시 내에서도 큰 그룹이 왼쪽에 위치하도록 정렬하자
그러면 Greedy 알고리즘에서 먼저 탑승한 택시는 아래쪽에 위치하게 된다
최적해 알고리즘도 아래쪽부터 배정한다고 가정하자

$s_{4}$이 탑승한 택시들을 모두 볼 때 Greedy와 최적해는 같다

$s_{3}$이 탑승한 택시들을 모두 볼 때, $s_{3}$가 모두 배정된 시점에 (Greedy의 여석) $\geq$ (최적해 여석)
즉, $s_{2}$를 배정하기 시작할 시점에 Greedy 알고리즘에서 배정해야 할 그룹이 더 적다

아직 배정하지 않은 택시들은 $s_{2},\ s_{1}$으로 최소 개수만큼 배정해야 한다
남은 그룹의 수는 (Greedy) $\geq$ (최적해) 이고 $s_{2}$은 $s_{1},\ s_{1}$으로 대체되므로
큰 그룹먼저 배정하면 최소 택시를 이용할 수 있다(well known greedy algorithm)

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, tmp;
    int cnt[5] {};
    cin >> n;
    while(n--){
        cin >> tmp;
        cnt[tmp]++;
    }
 
    tmp = min(cnt[1], cnt[3]);
    int taxi = tmp + cnt[2]/2 + cnt[4];
    cnt[2] %= 2;
    cnt[1] -= tmp;
    cnt[3] -= tmp;
    if(cnt[2] == 0 && cnt[1]) taxi += ceil((double) cnt[1]/4);
    else if(cnt[2] == 1 && cnt[1]) taxi += ceil((double) (cnt[1]-2)/4) + 1;
    else taxi += cnt[1] + cnt[2] + cnt[3];
 
    cout << taxi << endl;
 
    return 0;
}cs