[BOJ] 16471 작은 수 내기 바로가기
여자친구와 함께 보드게임카페에 간 주언이는, 여러 보드게임을 하며 데이트를 즐겼다. 3시간 커플세트로 결제를 하려던 순간, 주언이는 가격표 옆에 쓰여 있는 새로운 이벤트를 보았다.
바로 “사장님과의 게임에서 이기면 무료, 지거나 비기면 5000원 추가 지불” 이벤트였다. 보드게임에 자신이 있는 주언이는 사장님에게 게임 룰을 물어보았고, 그 룰은 다음과 같았다.
주언이는 자신이 이길 확률이 조금이라도 있을 경우 게임을 하고자 한다.
사장님이 받은 카드에 적힌 수들과, 주언이가 받은 카드에 적힌 수들이 주어질 때, 주언이가 게임을 해도 되는지 확인하자.
N값이 첫 번째 줄에 입력된다. (1 ≤ N < 100,000, N은 홀수)
주언이가 받은 카드 N장에 적힌 수들이 두 번째 줄에 입력된다.
사장님이 받은 카드 N장에 적힌 수들이 세 번째 줄에 입력된다.
주언이가 이길 확률이 조금이라도 있을 경우 “YES” 라고 출력하고,주언이가 이길 확률이 존재하지 않을 경우 “NO”라고 출력한다.
✍ 코드
from collections import deque
from sys import stdin
N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
B = list(map(int,stdin.readline().split()))
A.sort() # 오름차순 정렬
B.sort() # 오름차순 정렬
B = deque(B)
count = 0
for i in range(N): # 작은 값 순서대로
while B: # 모든 사장님 카드 확인
if B.popleft() > A[i]: # 사장님 카드보다 작은 카드라면
count += 1 # 승수 + 1
break
if count > (N // 2): # 승수가 N // 2 보다 크면
print("YES")
else: # 승수가 N // 2 보다 작다면
print("NO")