Python/Combination BOJ-14889 스타트와 링크

Posted on | In

[Python/Combination] BOJ-14889 스타트와 링크

📌문제링크 풀이참고

combinations 라이브러리만 이용하면 꽤나 간단하다.

하지만 라이브러리 없이 조합을 추출해 내는 방법을 익혀두는게 좋을 듯 하다.

1. combinations 라이브러리 사용한 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import combinations
N = int(input())
ability = [list(map(int,input().split())) for _ in range(N)]

combi = list(combinations(list(range(N)),N//2))
comblen = len(combi)
ans = float('inf')

for team in range(comblen // 2):
    startComb = list(combinations(combi[team],2))
    linkComb = list(combinations(combi[comblen-team-1],2))
    startTeam = linkTeam = 0;
    for player in startComb:
        startTeam += ability[player[0]][player[1]] + ability[player[1]][player[0]] 
    for player in linkComb:
        linkTeam += ability[player[0]][player[1]] + ability[player[1]][player[0]]
    diff = abs(startTeam - linkTeam)
    ans = min(ans,diff)
print(ans)

2. 라이브러리 사용하지 않은경우

📌문제링크

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# [모의 SW 역량테스트] 요리사
def dfs(idx, k) :
    global result
    if idx == N//2 :
        A=[]
        B=[]
        for i in range(N) :
            if not visit[i] :
                A.append(i)
            else :
                B.append(i)
        A_result = synergy(A)
        B_result = synergy(B)
        if result > abs(A_result - B_result) :
            result = abs(A_result - B_result) 
        return
    for i in range(k, N) :
        if visit[i] == 0 :
            visit[i] = 1
            dfs(idx + 1, i+1)
            visit[i] = 0

def synergy(combi) :
    score = 0
    for i in range(N//2) :
        for j in range(i+1, N//2) :
            score += graph[combi[i]][combi[j]] + graph[combi[j]][combi[i]]
    return score

T = int(input())
10
for testcase in range(T) :
    N =int(input())
    graph = [list(map(int, input().split())) for i in range(N)]
    visit = [0 for i in ran
             ge(N)]
    result = 9999999
    dfs(0,0)
    print('#{} {}'.format(testcase+1, result))

회고

근데, 채점이 90%까지 되다가 자꾸 틀렸다고 해서 꽤 시간을 잡아먹었다…

cnt = 1으로 둬서 생긴 문제였다 ^_^….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 문제의 코드
from itertools import combinations
N = int(input())
board = [list(map(int,input().split())) for _ in range(N)]

result = float('inf')
cnt = 0
items = [_ for _ in range(N,0,-1)]
combi_list = list(combinations(items,N//2))
check = int(len(list(combinations(items,N//2)))/2)

while 1:
    A=[];B=[];Start=0;link=0
    for _ in combi_list[cnt]:
        A.append(_)
    for _ in items:
        if _ in A :
            pass
        else :
            B.append(_)
    Start_list = list(combinations(A,2))
    link_list = list(combinations(B,2))
    for i in range(len(Start_list)) :
        sx,sy= Start_list[i][0]-1,Start_list[i][1]-1
        lx,ly= link_list[i][0]-1,link_list[i][1]-1
        Start += (board[sx][sy] + board[sy][sx])
        link += (board[lx][ly] + board[ly][lx])
    tmp_result = abs(Start-link)
    if result > tmp_result:
        result = tmp_result
    if cnt == (check-1) :
        break
    cnt += 1
print(result)

##