[백준/파이썬][Silver V] Code Guessing - 24586

[Silver V] Code Guessing - 24586

문제 링크

성능 요약

메모리: 108384 KB, 시간: 88 ms

분류

브루트포스 알고리즘, 많은 조건 분기

제출 일자

2025년 2월 24일 19:53:27

문제 설명

Alice and Bob are playing a board game with a deck of nine cards. For each digit between 1 to 9, there is one card with that digit on it. Alice and Bob each draw two cards after shuffling the cards, and see the digits on their own cards without revealing the digits to each other. Then Alice gives her two cards to Bob. Bob sees the digits on Alice’s cards and lays all the four cards on the table in increasing order by the digits. Cards are laid facing down.

Bob tells Alice the positions of her two cards. The goal of Alice is to guess the digits on Bob’s two cards. Can Alice uniquely determine these two digits and guess them correctly?

입력

The input has two integers p, q (1 ≤ p < q ≤ 9) on the first line, giving the digits on Alice’s cards. The next line has a string containing two ‘A’s and two ‘B’s, giving the positions of Alice’s and Bob’s cards on the table. It is guaranteed that Bob correctly sorts the cards and gives the correct positions of Alice’s cards.

출력

If Alice can uniquely determine the two digits on Bob’s cards, output the two digits on a single line, starting with the smaller digit. Otherwise, output -1.

풀이

def get_combinations(arr, k) :
    '''
    재귀(백트래킹)을 이용해 arr에서 크리 k의 모든 조합을 생성
    '''
    res = []
    def backtrack(start, curr) :
        if len(curr) == k :
            res.append(curr.copy())
            return
        for i in range(start, len(arr)) :
            curr.append(arr[i])
            backtrack(i + 1, curr)
            curr.pop()
    backtrack(0, [])
    return res

def sol_24586() :
    p, q = map(int, input().split())
    pattern = input().rstrip()

    remaining_cards = sorted(list(set(range(1, 10)) - {p, q}))

    candidate_pairs = get_combinations(remaining_cards, 2)

    valid_pairs = []
    for pair in candidate_pairs :
        x, y = pair
        cards = sorted([p, q, x, y])

        generated_pattern = ''.join('A' if card in (p, q) else 'B' for card in cards)
        if generated_pattern == pattern :
            valid_pairs.append(tuple(sorted(pair)))

    if len(valid_pairs) == 1 :
        print(valid_pairs[0][0], valid_pairs[0][1])
    else :
        print(-1)

sol_24586()

Alice는 $a$와 $b$ (단, $a < b$)를 알고 있다. Bob이 제시한 패턴 문자열을 보면, 정렬된 4장의 카드 중 Alice의 카드 위치를 알려주고 Alice가 Bob의 카드를 확정된 하나의 카드 페어를 맞추면 되는 게임이다.

1. Alice 카드의 위치에 따른 제약 :
   • 만약 Bob의 카드가 Alice의 카드보다 앞쪽(왼쪽)에 놓이면, 그 카드의 숫자는 Alice의 카드보다 작아야 한다.
   • 만약 Bob의 카드가 Alice의 카드 사이에 놓이면, 그 카드의 숫자는 두 Alice 카드 사이에 있어야 한다.
   • 만약 Bob의 카드가 Alice의 카드보다 뒤쪽(오른쪽)에 놓이면, 그 카드의 숫자는 Alice의 카드보다 커야 한다.
2. 사용 가능한 숫자 :
   • 전체 숫자 1 ~ 9 중, Alice가 가진 숫자는 이미 사용되었으므로 Bob이 받을 수 있는 숫자는 나머지 7개 중에서 선택
3. 유일 결정 조건 :
   • 위 제약 조건을 만족하는 Bob의 카드의 두 숫자에 대해 가능한 조합이 단 하나여야 한다.
   • 만약 여러 가능한 조합이 있다면, Alice는 Bob의 카드 숫자를 유일하게 결정할 수 없으므로 답은 -1

백트래킹으로 조합 구하기.

def get_combinations(arr, k) :
    '''
    재귀(백트래킹)을 이용해 arr에서 크리 k의 모든 조합을 생성
    '''
    res = []
    def backtrack(start, curr) :
        if len(curr) == k :
            res.append(curr.copy())
            return
        for i in range(start, len(arr)) :
            curr.append(arr[i])
            backtrack(i + 1, curr)
            curr.pop()
    backtrack(0, [])
    return res

백트래킹을 활용하여 2자리 숫자의 조합을 찾는다. 이거 한 번 알아놓으면 좋은 로직인 것 같다.

나머지는 위 로직을 한 번 찬찬히 읽어보면 이해가 될 코드라고 생각한다.