[백준/11968/파이썬] High Card Wins

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

11968번: High Card Wins

Problem

소 Bessie는 카드게임을 좋아합니다. 놀랍게도, Bessie에게 카드를 쥘 손이 없지만요.(??) 불행히도, 다른 소 친구들은 좋은 적수가 되지 못합니다.(상대가 되지 않는다는 뜻이겠죠?) 그들은 나빠서(바보라서) 완벽하게 항상 예측이 가능한 방식으로 플레이를 합니다. 하지만, 그럼에도 베시가 상대편을 이기기 위한 방법을 알아내는건 큰 도전입니다. (의미가 없지 않습니다)

1~ 2N이 적혀있는 카드를 N장씩 나눠갖고,N라운드 마다, Bessie와 Elsie의 카드를 비교하고, 승자를 가리는 게임을 하려고 합니다.

Bessie가 Elsie의 카드를 완전히 예측가능하다고 할 때, Bessie가 얻을 수 있는 승점은?

조건

The first line of input contains the value of N (1≤N≤50,000).

The next N lines contain the cards that Elsie will play in each of the successive rounds of the game. Note that it is easy to determine Bessie's cards from this information.

SOL

영어로 된 문제를 풀어봤다. 여기서 문제가 발생해서 해맸던 곳이 매 판마다 카드를 비교하는 방식이다.

즉, 서로 비교가 끝나면 그 카드는 없는 패가 되버린다.

이게 말로 설명하면 이해가 확 되지 않는데, 예시를 하나 들면 빠르게 이해가 가능하다.

 

예를들어, Elsie = [1,2,6] 이 있고 , B=[3,4,5] 가 있다고 합시다.

 

이때, Elsie는 1,2,6 중에 1개를 낼 수 잇고, Bessie는 3,4,5 중에 1개를 낼 수 있습니다. 하지만, Bessie는 엄청난(천년아이)능력이 있기 때문에, Elsie의 카드를 정확히 예측 가능합니다. 

즉, Elsie의 차례가 고정되었다고 봐도 무방하겠죠. 편의상 오름차순으로 낸다고 합시다.

 

Elsie = 1 , Bessie = 2

Elsie = 3 , Bessie = 4

Elsie = 6 , Bessie = 5 

로 총 2점을 획득하게 될겁니다. 

 

이런 경우는 어떨까요

E =[1,4,6] , B=[2,3,5]

 

Elsie =1 , Bessie = 2

 

Elsie = 4 , Bessie = 5 (3은 pass) << 이 3을 pass하는 부분을 잘 생각해야한다.

Elsie = 6 , Bessie = 3

 

즉, elsie보다 작다면, Bessie는 오름차순으로 정리된 거에서 다음거부터 먼저 내는 합법적인 기술을 사용할 수 있다.

그리고나서, elsie와 또 비교하면 된다.

import sys
input= sys.stdin.readline
N=int(input().rstrip())

card=[0 for _ in range(2*N+1)]

E=[]
B=[]
for _ in range(N):
    a=int(input().rstrip())
    card[a]=1

for i in range(1,len(card)):
    if card[i]:
        E.append(i)
    else:
        B.append(i)
e,b=0,0
ans=0
while b<N and e<N:
    if (B[b]>E[e]):
        ans+=1
        b+=1
        e+=1
    else:
        b+=1
print(ans)