백준 1671(상어의 저녁식사) 풀이

기본적인 이분매칭이었습니다.

 

solved.ac 티어: 플래티넘 3

www.acmicpc.net/problem/1671

1671번: 상어의 저녁식사

 

일단 이문제는 이분매칭 문제이기 때문에 이분매칭을 할수있어야 한다. 열혈강호 문제를 풀어보고 오자.

www.acmicpc.net/problem/11375

11375번: 열혈강호

이 문제를 풀고 왔다면 이제 풀이를 설명하겠다.

문제 설명에 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다

능력치가 모두 같은 상어 A, B가 있다면 A가 B를, B가 A를 잡아먹을 수는 있지만 A, B가 서로 잡아먹을수는 없다.

 

이렇게 써있는데 이러면 입력을 받고 2중반복을 하면서 배열에 한쪽이 크기,속도,지능이 더 크다면 해당하는 위치에 넣고 반대쪽이 더 크면 반대쪽의 해당하는 위치에 넣으면 된다. 만약 3개 다 같을경우 아무곳이나 넣어도 상관없다

 

그리고 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 이라도 되어있기 때문에 이분매칭을 실행하는 코드를 2번 반복해주고 이때 나오는 값은상어가 죽는 수중 최댓값이기 때문에 N-최댓값을 해주면 맞았습니다가 뜬다.

 

 

import sys
def dfs(x):
    for i in range(len(l[x])):
        y=l[x][i]
        if t[y]:continue
        t[y]=True
        if q[y]==0 or dfs(q[y]):
            q[y]=x
            return False
    return True
input=sys.stdin.readline
a=int(input())
m=[list(map(int,input().split())) for i in range(a)]
l=[[] for i in range(91)]
for i in range(a):
    for g in range(i+1,a):
        if m[i][0]==m[g][0] and m[i][1]==m[g][1] and m[i][2]==m[g][2]:l[i+1].append(g+1)
        elif m[i][0]>=m[g][0] and m[i][1]>=m[g][1] and m[i][2]>=m[g][2]:l[i+1].append(g+1)
        elif m[g][0]>m[i][0] and m[g][1]>m[i][1] and m[g][2]>m[i][2]:l[g+1].append(i+1)
q=[0]*101
t=[0]*101
cnt=0
for qt in range(1):
    for i in range(a):
        t=[False]*101
        if dfs(i+1):cnt+=1
print(a-cnt)

 (원래 코드 가독성을 무시하고 짜니 이해부탁립니다)