https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg#

에서 토너먼트 카드게임

첫번째 시도

• 2명씩 대진 시켜서 다음 대진 리스트를 만듬, 마지막 혼자 남을 시 부전승처리

• 실패- 테스트케이스 10개중 4개 통과

  • 문제랑 편성자체가 달라서 부전승이 누가 처리 되는지가 다름

  • 예시) 6명 일경우 -> 문제에서 3/3 -> 2/1/2/1 로 팀평성 처리가 되는데

    현재 알고리즘상으로는 2/2/2 로 대진표가 짜지기 때문에 실제 대진이 달라짐

import sys
sys.stdin = open("input.txt")

T = int(input())

# 왠지모르겠는데 10개중 4개 테스트 케이스 통과
for tc in range(1, T+1):
    N = int(input())
    inp_arr = list(map(int, input().split()))

    def func(arr) : # 매개 -누구랑 누구가 뜨는지 인덱스 리스트

        if len(arr) ==1 :
            return arr[0]

        next_arr = [0] * ((len(arr)+1)//2) # 새로운 승자 인덱스 리스트
        for i in range(0,len(arr),2) :
            front = inp_arr[ arr[i] ]
            try :
                end = inp_arr[ arr[i+1] ]
            except : # 만약 마지막에 대결할 상대가 없을경우

                next_arr[i//2] = arr[i]
                continue

            result = (front-end +3 ) %3 # 0 :비김 1 :front승  2:end승
            if result ==0 :
                next_arr[i//2] = arr[i] # 비기면 번호가 작은 애가 이김
            elif result == 1: # front 승
                next_arr[i//2] = arr[i]
            else : # end 승
                next_arr[i//2] = arr[i+1]

        return func(next_arr)

    result = func(range(N))
    result +=1 # 인덱스 맞춰주기( 문제에서는 1부터 시작하므로)

    print("#{} {}".format(tc, result))

두번째 시도

• 문제의 말 그대로를 코드화 시킴 - 분할정복

import sys
sys.stdin = open("input.txt")

T = int(input())

def win(x,y) :
    first = inp_arr[x]
    second = inp_arr[y]
    if (first-second+3)% 3 == 2 : # y의 승리
        return y
    else : # x 승리, 비김
        return x

def func(start, end) :
    if start == end :
        return start

    first = func(start, (start+end)//2)
    second = func((start+end)//2+1, end)
    return win(first, second)

for tc in range(1, T+1):
    N = int(input())
    inp_arr = list(map(int, input().split()))
    result = func(0, N-1)
    result+=1 # 인덱스 맞춰주기
    
    print("#{} {}".format(tc, result))