[백준, SWEA] BOJ 14889 스타트와 링크, swea4012 요리사

https://acmicpc.net/problem/14889 

14889번: 스타트와 링크

n = int(input())
s_ij = [list(map(int, input().split())) for i in range(n)]
min_val = 100 * 20

visit = [0] * n
def comb(index=0, arr=[]):
    if index == (n // 2):
        global min_val
        value = total_chk(arr)
        if min_val > value:
            min_val = value
    else: #
        tmp_index = arr[-1] if arr else index
        for i in range(tmp_index, n):
            if visit[i]: continue
            visit[i] = 1
            comb(index + 1, arr+[i])
            visit[i] = 0

def total_chk(arr):
    total = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            total += s_ij[arr[i]][arr[j]] + s_ij[arr[j]][arr[i]]
    arr2 = list(set(range(n)) - set(arr))
    total2 = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            total2 += s_ij[arr2[i]][arr2[j]] + s_ij[arr2[j]][arr2[i]]
    result = abs(total-total2)
    return result

comb()
print(min_val)

 

n개의 원소를 가진 집합에서 원소개수의 반을 가지는 부분집합을 구하는 문제이다. nC(n//2)

부분집합을 백트래킹을 사용해서 구했고, 부분집합을 인자로 넘겨서 팀 능력치의 차이를 구했다.

하나의 부분집합을 구하면 반대편의 집합도 구할수 있다. 'arr2 = list(set(range(n)) - set(arr))'

백준 solved.ac 골드 찍었다 헤헿

1학기안으로 플래찍을수 있겠지?

---

swea 4012 [모의sw역량테스트] 요리사

이 문제랑 완전히 똑같다 복붙해서 냈더니 통과

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    s_ij = [list(map(int, input().split())) for i in range(n)]
    min_val = 100 * 20

    visit = [0] * n
    def comb(index=0, arr=[]):
        if index == (n // 2):
            global min_val
            value = total_chk(arr)
            if min_val > value:
                min_val = value
        else: #
            tmp_index = arr[-1] if arr else index
            for i in range(tmp_index, n):
                if visit[i]: continue
                visit[i] = 1
                comb(index + 1, arr+[i])
                visit[i] = 0

    def total_chk(arr):
        total = 0
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                total += s_ij[arr[i]][arr[j]] + s_ij[arr[j]][arr[i]]
        arr2 = list(set(range(n)) - set(arr))
        total2 = 0
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                total2 += s_ij[arr2[i]][arr2[j]] + s_ij[arr2[j]][arr2[i]]
        result = abs(total-total2)
        return result

    comb()
    print("#{} {}".format(test_case, min_val))