[백준]상어의 저녁식사(1671)

문제 링크 : [백준]상어의 저녁식사(1671)

문제 설명

N마리의 상어의 세가지 능력치가 주어집니다.
상어끼리 세가지 능력 모두 크거나 같다면 다른 상어를 잡아먹을 수 있습니다.
상어가 최소로 남아있을 때의 마릿수를 구하세요.

입력

N(상어 수, 1 <= N <= 50)
A1_i
A2_i
A3_i(상어의 능력치, 1 <= A1~3_i <= 2,000,000,000)

5
4 5 5
10 10 8
5 7 10
8 7 7
8 10 3

출력

2

카테고리

#이분매칭

시간 복잡도 상한

O(N³)

해결 방법

1. 최소의 수가 남아야 한다는 것은, 반대로 상어끼리 최대한 먹을 수 있는 수를 구하면 됩니다.
2. 모든 상어들을 먹는 상어 -> 먹히는 상어의 관계로 그래프로 나타냅니다.
3. 먹는 상어와 먹히는 상어는 이분 그래프로 나타나게 됩니다.
4. 이분 그래프에서 최대한 많이 먹을 수 있는, 즉 최대한 많이 매핑을 시키려면 이분 매칭으로 상어들을 매칭시킵니다.
5. 일반적인 이분매칭과는 다르게 상어 한마리가 최대 두마리씩 잡아먹을 수 있습니다.
6. 이 부분은 상어 한마리에 대해 두번씩 DFS를 돌려서 해결 할 수 있습니다.
7. 단, 두 상어의 능력치가 동일할 경우, 서로 잡아먹는 경우가 발생합니다.
8. 5를 막기 위하여, 두 상어의 능력치가 동일하다면 상어의 인덱스로 단방향(예시 : i < j)으로만 엣지가 생성되도록 합니다.

시간복잡도

O(N*N)

코드

#include<cstdio>
#include<string.h>
int n,k,e[51],f[51],t,i,j;
int r(int p){
    if(e[p])return 0;
    e[p]=1;
    for(int i=p;i<=n;i+=k){
        if(!f[i]||r(f[i])){
            f[i]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&k);
    for(;i<n;i++){
        memset(e,0,sizeof(e));
        scanf("%d",&t);
        j+=r(t);
    }
    printf("%d",j==n);
}