[백준 16471번] 작은 수 내기 (Python)

> 파이썬, 그리디 알고리즘, 정렬

 

 

 

 

📖 문제 : 작은 수 내기 (Python)

 

 

여자친구와 함께 보드게임카페에 간 주언이는, 여러 보드게임을 하며 데이트를 즐겼다. 3시간 커플세트로 결제를 하려던 순간, 주언이는 가격표 옆에 쓰여 있는 새로운 이벤트를 보았다. 

바로 “사장님과의 게임에서 이기면 무료, 지거나 비기면 5000원 추가 지불” 이벤트였다. 보드게임에 자신이 있는 주언이는 사장님에게 게임 룰을 물어보았고, 그 룰은 다음과 같았다. 

1. 각자 N장의 카드를 받는다. (N은 홀수다) 
2. 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다)
3. 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 경우, 둘 다 점수를 획득하지 못한다)
4. 총 N번의 승부 후, (N+1)/2점 이상의 점수를 획득한 사람이 승리한다.
5. (N+1)/2점 이상의 점수를 획득한 사람이 없을 경우, 승자가 없는 것으로 게임이 끝난다. 

주언이는 자신이 이길 확률이 조금이라도 있을 경우 게임을 하고자 한다. 

사장님이 받은 카드에 적힌 수들과, 주언이가 받은 카드에 적힌 수들이 주어질 때, 주언이가 게임을 해도 되는지 확인하자. 

 

입력

N값이 첫 번째 줄에 입력된다. (1 ≤ N < 100,000, N은 홀수)

주언이가 받은 카드 N장에 적힌 수들이 두 번째 줄에 입력된다.

사장님이 받은 카드 N장에 적힌 수들이 세 번째 줄에 입력된다. 

 

출력

주언이가 이길 확률이 조금이라도 있을 경우 “YES” 라고 출력하고,주언이가 이길 확률이 존재하지 않을 경우 “NO”라고 출력한다.

 

예제 입력 1 

5
2 1 3 5 6
1 1 3 2 5

 

예제 출력 1 

YES

 

 

힌트

• 주언이: 2 사장님: 3
• 주언이: 1 사장님: 2
• 주언이: 3 사장님: 5

예제 입력 1에 대해 위와 같이 내는 경우, 주언이가 3점을 획득하여 게임에서 이기는 경우의 수가 생긴다. 주언이가 이기는 확률이 있기 때문에, YES를 출력한다. 

 

 

 

내 코드

N = int(input())
mine = list(map(int, input().split()))
boss = list(map(int, input().split()))

mine.sort()
boss.sort()

m = 0
b = 0
win = 0

while m < N and b < N:
    if mine[m] < boss[b]:
        win += 1
        m += 1
        b += 1
    else:
        b += 1

if win >= (N + 1) // 2:
    print("YES")
else:
    print("NO")

 

 

Point ! ⭐️ 

• 더 작은 수를 내어 주안이가 사장님을 이겨 1점씩 점수를 얻을 수 있는데, 총 얻을 수 있는 점수가 (N+1)/2보다 크면 YES, 아니면 NO를 출력해야하는 문제입니다.
  
  주안이와 사장님의 카드를 정렬하여 맨 처음부터 서로 비교해가며 경우에 따라,
  1. 현재 주안이의 카드 번호가 현재 사장님의 카드 번호보다 작아서 점수를 1점 얻을 수 있을 때, 
     win 변수의 값을 +1, 주안이와 사장님의 인덱스도 +1
  2. 현재 주안이의 카드 번호가 현재 사장님의 카드 번호보다 크거나 같으면,
     사장님의 인덱스 번호만 +1 합니다.
  주안이가 점수를 얻을 수 있는 카드가 나올 때까지 사장님의 인덱스 번호만 +1 해나갑니다. (사장님의 인덱스 번호를 +1 해나가면, 사장님의 카드 번호는 점점 커지므로, 정렬을 했기 때문에)

 

 

 

 

백준

https://www.acmicpc.net/problem/16471

16471번: 작은 수 내기