https://school.programmers.co.kr/learn/courses/30/lessons/258707

6n개의 카드가 있고, 거기서 1/3을 먼저 갖고 있고, 코인도 coin개가 있을 때, 매 라운드마다 2장의 카드를 뽑고 가지려면 각각 코인 한 개씩 써야한다. 그리고 라운드마다 6n+1을 맞춰서 카드를 2장 제출해야하는데 제출 못하면 경기 끝일 때 라운드 최대가 되도록 하는 문제이다.

Python

시도 1 - 실패

def solution(coin, cards):
    answer = 0
    n = len(cards)
    target = n + 1

    cur = sorted(cards[:n // 3])  # 초기 cur 리스트는 정렬된 상태
    cards = cards[n // 3:]
    cards.reverse()

    answer = dfs(list(cards), list(cur), coin, 1, target)
    return answer


def dfs(cards, cur, coin, r, target):
    ans = r
    if not cards:
        return ans

    new1 = cards.pop()
    new2 = cards.pop() if cards else None
    cur.sort()

    found = []
    need = []

    start, end = 0, len(cur) - 1
    while start < end:
        s = cur[start] + cur[end]

        if s == target:
            found.append((start, end))
            start += 1
            end -= 1
        elif s < target:
            start += 1
        else:
            end -= 1

        if cur[start] + new1 == target:
            need.append((new1, start))
        if new2 and cur[start] + new2 == target:
            need.append((new2, start))
        if cur[end] + new1 == target:
            need.append((new1, end))
        if new2 and cur[end] + new2 == target:
            need.append((new2, end))

    for start, end in found:
        cur_next = cur[:start] + cur[start + 1:end] + cur[end + 1:]

        ans = max(ans,
                  dfs(list(cards + [new1, new2] if new2 else [new1]), cur_next, coin, r + 1, target),
                  dfs(list(cards + [new2] if new2 else []), cur_next + [new1], coin, r + 1, target),
                  dfs(list(cards + [new1]), cur_next + [new2] if new2 else [], coin, r + 1, target))

    if coin > 0:
        for new, idx in need:
            cur_next = cur[:idx] + cur[idx + 1:]

            if new == new1:
                ans = max(ans,
                          dfs(list(cards + [new2] if new2 else []), cur_next, coin - 1, r + 1, target),
                          dfs(list(cards), cur_next + [new2] if new2 else [], coin - 1, r + 1, target))
            elif new == new2:
                ans = max(ans,
                          dfs(list(cards + [new1]), cur_next, coin - 1, r + 1, target),
                          dfs(list(cards), cur_next + [new1], coin - 1, r + 1, target))

    if coin > 1 and new2 and new1 + new2 == target:
        ans = max(ans, dfs(list(cards), cur, coin - 2, r + 1, target))

    return ans

문제의 조건에 충실하게 접근했다. DFS로 매 라운드마다 일단 카드 두 장을 뽑고, 현재 갖고 있는 카드 중에서 n+1을 조합할 수 있는지 확인했다. 확인하면서 모든 카드에 대해서 새로 뽑은 카드와의 조합으로 n+1을 만들 수 있는지도 확인했다.

그리고 모든 경우에 대해서

현재 조합의 카드를 사용할 경우 * (새 카드 모두 버림, 새 카드 중 하나만 가짐, 새 카드 모두 가짐)

새 카드 중 하나만 쓸 경우 * (나머지 카드 버림, 나머지 카드도 가짐)

새 카드 둘을 써서 조합할 경우

이렇게 각 경우에 대해서 DFS를 진행했고, 테스트 케이스는 2개가 틀리고 전체 테스트에서는 대부분 시간초과가 발생했다.

시도 2

어차피 이 카드 조합이 1~n까지라서 n+1을 만드는 조합은 하나밖에 없기 때문에 무조건 빨리 제거하는 것이 최선이다.
나는 지금 갖고 있는 카드 조합에서 나오는 경우라도 혹시나 새로 뽑은 카드 조합에서 나올 수도 있기에 그 경우까지 계산했다.

https://tolerblanc.github.io/programmers/programmers-nplueone-cardgame/
그리고 이 글을 참고하면서 깨달은 것은 매번 카드 뽑고 버렸는데, 굳이 안 그래도 갖고 있다가 나중에 필요하면 코인써서 가져와도 된다는 것이다.
실제 게임이라면 그러면 안 되지만 여기서는 최선의 경우를 찾는 것이기에 카드를 버린다는 규칙은 무시해도 된다는 것을 생각하지 못했다.

def solution(coin, cards):
    answer = 1
    n = len(cards)
    target = n+1
    cur = cards[:n//3]
    
    cards = list(reversed(cards[n//3:]))
    
    new = []
    
    def check(cards1, cards2):
        cardSet = set(cards2)
        for card in cards1:
            if target - card in cardSet:
                cards1.remove(card)
                cards2.remove(target-card)
                return True
        return False
    
    while coin >= 0 and cards:
        new.append(cards.pop())
        new.append(cards.pop())
        
        
        if check(cur, cur):
            pass
        elif coin >= 1 and check(cur, new):
            coin -= 1
        elif coin >= 2 and check(new, new):
            coin -= 2
        else:
            break
        answer += 1
        
    return answer