[프로그래머스] [C++] 체육복 (네트워크 플로, 탐욕법)

1. 문제

반 학생들의 체육복이 도난당했다.

 

도난당한 학생의 번호와 여유분을 가진 학생의 번호가 주어진다.

 

여유분을 가진 학생이 도난당한 학생에게 체육복을 빌려줄때

 

체육복을 최대한 나눠주고, 체육수업을 들을 수 있는 최대 학생수를 구하여라

 

단, 체육복은 자신의 앞뒤 번호한테만 빌려줄 수 있다.

 

단, 여유분을 가지고 있던 학생이 도난당했을 수 있다. 그러면 빌려주지 않는다.

 

2. 자원분배 문제: 네트워크 플로

이 문제는 이분 그래프의 최대매칭 문제로 네트워크 플로로 풀 수 있다.

 

여유분 그룹에서 도난 그룹으로가는 그래프를 그린 후 네트워크 플로우 알고리즘을 사용하면 문제가 해결된다.

 

단, 여유분을 가지고 있던 학생이 도난당할경우 그래프를 그리지 않는다.

 

int networkflow(int src, int sink, vector<vector<int> >& capa)
{
    int ret = 0, V = capa.size();
    vector<vector<int> > flow(V, vector<int>(V, 0));
    
    while(true)
    {
        vector<int> parent(V, -1);
        queue<int> q;
        parent[src] = src;
        q.push(src);
        while(!q.empty()&& parent[sink] == -1)
        {
            int here = q.front(); q.pop();
            for(int there = 0; there < V; there++)
                if(parent[there] == -1 && capa[here][there] - flow[here][there]>0)
                {
                    q.push(there);
                    parent[there] = here;
                }
        }
        if(parent[sink] == -1) break;
        for(int p = sink; p != src; p = parent[p])
            flow[parent[p]][p] += 1;
        ret += 1;
    }
    return ret;
}
int solution1(int n, vector<int>& lost, vector<int>& reserve)
{
    vector<vector<int> > capa = vector<vector<int> >(n+2, vector<int>(n+2, 0));
    int lostStudent = 0;
    for(int i = 0; i < reserve.size(); i++)
            capa[0][reserve[i]] = 1;
    
    for(int i = 0; i < lost.size(); i++)
        if(capa[0][lost[i]] != 1)
        {
            lostStudent++;
            capa[lost[i]][n+1] = 1;
        }
        else
            capa[0][lost[i]] = 0;
        
    for(int i = 0; i < reserve.size(); i++)
    {
        if(reserve[i]-1 < n-1 && capa[0][reserve[i]] == 1)
            capa[reserve[i]][reserve[i]+1] = 1;
        if(reserve[i]-1 > 0 && capa[0][reserve[i]] == 1)
            capa[reserve[i]][reserve[i]-1] = 1;
    }
    return networkflow(0, n+1, capa) + n - lostStudent;
}

 

3. 그리디

이 문제는 또한 탐욕법으로도 풀 수 있다.

 

바로 양옆사람한테만 나눠줄 수 있기 때문이다.

 

이 문제는 트리의 지배 집합찾기 문제와 유사하다

 

위 링크의 문제에서는 트리의 '리프' 부터 시작하여 문제를 해결하였다.

 

이 문제도 또한 1번부터 차례대로 왼쪽 부터 주는 순서로 체육복을 주게되면

 

결국 최대한 많이 체육복을 나눠주게 된다.

 

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    vector<int> student(n, 0);
    for(int i = 0 ; i < lost.size() ; i++)
        student[lost[i]-1]--;
    for(int i = 0; i < reserve.size(); i++)
        student[reserve[i]-1]++;
    for(int i = 0; i < n; i++)
        if(student[i] < 0)
        {
            if(0 < i && student[i-1] > 0)
                student[i-1]--;
            else if(i < n-1 && student[i+1] > 0)
                student[i+1]--;
            else 
               answer--;
        }
    return answer;
}

 

Algorithm/GymClothes.cpp at master · Nor-s/Algorithm (github.com)

Nor-s/Algorithm

 

코딩테스트 연습 - 체육복 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 체육복