SWE(4880)_토너먼트 카드게임

작성일 | In

SWE 4880 토너먼트 카드게임

문제

가위바위보가 그려진 카드를 이용, 토너먼트로 한 명을 뽑는다.

1~N까지 N명의 학생들이 N장의 카드를 나눠 갖음

전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 ,이긴 사람이 최종 승자 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 다음처럼 두개로 나눈다. i~ (i+j)//2 | (i+j)//2+1 ~ j

두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식 다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 짝은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다.

N명의 학생들이 카드를 골랐을 때, 1등을 찾는 프로그램을 만드시오

문제이해 : 분할 정복과 가위바위보의 크로스다.

  1. 우선 분할 한다.
  2. 분할 한뒤 계산하면서 승자 합친다.
# 가위 바위보 판별 함수
def win(x, y):
    # 1은 가위 2는 바위 3은 보
    if (lst[x-1] == 1 and lst[y-1] == 3) or (lst[x-1] == 1 and lst[y-1] == 1):
        return x
    elif (lst[x-1] == 2 and lst[y-1] == 1) or (lst[x-1] == 2 and lst[y-1] == 2):
        return x
    elif (lst[x-1] == 3 and lst[y-1] == 2) or (lst[x-1] == 3 and lst[y-1] == 3):
        return x
    return y

# 수를 나누는 재귀함수


def match(start, end):
    if start == end:
        return start
    first_value = match(start, (start+end)//2)
    second_value = match((start+end)//2+1, end)
    return win(first_value, second_value)


TC = int(input())

for tc in range(1, TC+1):
    N = int(input())
    lst = list(map(int, input().split()))
    start = 1
    end = N
    print(f'#{tc} {match(start,end)}')
  • 아주 기본적인 문제다.
  • 트리구조를 그려가면서 BFS,DFS에 접근하는게 좋겠다.

참고한 코드

[참고한 블로그 ]https://tothefullest08.github.io/algorithm/2019/02/25/4880_tournament/

– 참고자료

0%