SWE(토너먼트,배열최소합)복습

작성일 | In

토너먼트 카드게임

def win(x, y):
    if (arr[x] == 1 and arr[y] == 3) or (arr[x] == 1 and arr[y] == 1):
        return x
    elif (arr[x] == 2 and arr[y] == 1) or (arr[x] == 2 and arr[y] == 2):
        return x
    elif (arr[x] == 3 and arr[y] == 2) or (arr[x] == 3 and arr[y] == 3):
        return x
    return y


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


for rounds in range(int(input())):
    N = int(input())
    arr = [0]+list(map(int, input().split()))
    result = match(1, N)
    print(f"#{rounds+1} {result}")

배열최소합

def DFS(row):
    global result, sub_result
    if result < sub_result:
        return

    if row == N:
        if sub_result < result:
            result = sub_result
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            sub_result += arr[row][i]
            DFS(row + 1)
            visited[i] = False
            sub_result -= arr[row][i]


for rounds in range(int(input())):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0]*N
    sub_result, result = 0, 999999999
    DFS(0)
    print(f"#{rounds+1} {result}")
  • 방문했던 곳 다시 초기화 해주고, sub_result도 갱신해주고, DFS(row+1)이 관건이다.

참고자료 [SWexperacademy]https://swexpertacademy.com

0%