5일차 - 토너먼트 카드게임

def who_is_winner(f, r):
    x = card[f]
    y = card[r]

    if x == 1:
        if y == 1 or y == 3:
            return [f]
        else:
            return [r]
    elif x == 2:
        if y == 2 or y == 1:
            return [f]
        else:
            return [r]
    else:
        if y == 3 or y == 2:
            return [f]
        else:
            return [r]

def divide(arr):
    if len(arr) == 1:
        return arr
    
    i = 1
    j = len(arr)
    mid = (i+j) // 2

    front = arr[:mid]
    rear = arr[mid:]

    front = divide(front)
    rear = divide(rear)

    return who_is_winner(front[0], rear[0])

for i in range(int(input())):
    n = int(input())
    card = list(map(int, input().split()))

    print(f"#{i+1} {divide([i for i in range(n)])[0] + 1}")

 

난이도 D2인데 못짜겠어서 인터넷 봤습니다!

 

분할정복인데 분할까진 어찌 하겠는데 통합을 못시키겠어서 많이 고민했던 문제.. 얘때문에 다른 문제도 많이 못풀고 시간 지체 많이됨ㅠ

 

손디버깅하면서 작동 원리 이해하고 분할정복 다른 문제 풀러 가보도록 하겟슴