n+1카드게임.PY

from collections import deque

def check(cards, candidates, target):
    for card in cards:
        # 새로 들어온 카드를 써서 낼 수 있는 경우
        if target - card in candidates:
            candidates.remove(target-card)
            cards.remove(card)
            return True
    return False


def solution(coin, cards):
    # 처음에 카드 n/3장 가져간다.
    # 매 턴, 손에 들어온 카드는 버릴 필요가 없다. 어차피 2장씩 고정으로 빠지고, 남은 게 없으면 턴이 끝난다
    n = len(cards)
    my_card = set(cards[:len(cards) // 3])
    left_card = deque(cards[len(cards)//3:])
    
    candidates = set()
    rounds = 1
    while coin >= 0 and left_card:
        candidates.add(left_card.popleft())
        candidates.add(left_card.popleft())
        
        # 1. 코인 손실 없이, 가지고 있는 카드만으로 내는 게 최선
        if check(my_card, my_card, n+1):
            pass
        # 2. 코인 1개로 턴을 넘길 수 있는지
        elif coin >= 1 and check(my_card, candidates, n+1):
            coin -= 1
        elif coin >= 2 and check(candidates, candidates, n+1):
            coin -=2
        else:
            # 더 이상 턴을 진행할 수 없다
            break
        
        rounds += 1
    
    return rounds