문제 정보
문제 정리
남자와 여자가 각각 N명씩 있다. 어떤 남자들은 자기보다 키가 큰 여자와 춤을 추고 싶어하며, 어떤 남자들은 자기보다 키가 작은 여자와 춤을 추고 싶어한다. 여자도 마찬가지이다. 남녀 모두 조건을 만족할 때, 만들 수 있는 매칭의 개수의 최대값을 구하는 문제이다.
풀이
매칭이 가능한 경우를 생각해보자.
1. 남자(자신보다 큰 여자 선호) + 여자(자신보다 큰 남자 선호)
2. 남자(자신보다 큰 여자 선호) + 여자(자신보다 작은 남자 선호)
3. 남자(자신보다 작은 여자 선호) + 여자(자신보다 큰 남자 선호)
4. 남자(자신보다 작은 여자 선호) + 여자(자신보다 작은 남자 선호)
이렇게 4가지로 볼 수 있다.
그 중 1번과 4번은 남자와 여자 중 한 명은 반드시 원하는 사람과 매칭될 수 없으므로 불가능한 케이스가 된다.
따라서, 2번 케이스로 가능한 최대값, 3번 케이스로 가능한 최대값을 각각 구해 더해주면 답이 된다.
2번 케이스의 경우, 양수 값을 가진 남자들을 따로 저장하여 정렬, 음수 값을 가진 여자들을 따로 저장하여 정렬한다.
양수 값을 가진 사람은 (키, INF]인 구간으로, 음수 값을 가진 사람은 [0, 키)인 구간으로 볼 수 있으며, 끝점이 뒤쪽에 있는 구간부터 그리디하게 매칭해주면 된다.
2번 케이스, 3번 케이스를 for문으로 합쳐서 압축할 수 있는데 귀찮아서 그냥 복붙해서 변수명만 바꿨다...
코드
# 백준 2831
import io
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
def solve(N, man, woman):
manPlus = []
womanPlus = []
manMinus = []
womanMinus = []
for i in range(N):
if man[i] > 0:
manPlus.append(man[i])
else:
manMinus.append(man[i])
if woman[i] > 0:
womanPlus.append(woman[i])
else:
womanMinus.append(woman[i])
manPlus.sort()
womanPlus.sort()
manMinus.sort()
womanMinus.sort()
# 1. (자신보다 큰 여자 선호) + (자신보다 작은 남자 선호) 매칭
manI = len(manPlus)-1
womanI = 0
result = 0
while manI >= 0 and womanI < len(womanMinus):
curM = manPlus[manI]
curW = womanMinus[womanI]
# 남자의 요구조건이 큰 경우
if curM >= -curW:
manI -= 1
# 매칭이 가능한 경우
else:
result += 1
manI -= 1
womanI += 1
# (자신보다 작은 여자 선호) + (자신보다 큰 남자 선호) 매칭
womanI = len(womanPlus)-1
manI = 0
while womanI >= 0 and manI < len(manMinus):
curM = manMinus[manI]
curW = womanPlus[womanI]
# 여자의 요구조건이 큰 경우
if curW >= -curM:
womanI -= 1
# 매칭이 가능한 경우
else:
result += 1
womanI -= 1
manI += 1
return result
def main():
N = int(input())
man = list(map(int, input().split()))
woman = list(map(int, input().split()))
print(solve(N, man, woman))
main()
