[Python] 백준 14889번: 스타트와 링크 - brute force

문제

14889번: 스타트와 링크

풀이

처음 인풋으로 받은 배열중 상단 삼각형에 두 경우의 합을 저장했고,

combinations()를 사용해 N/2명의 조합을 만들고, 그 조합에 포함되지 않은 사람들의 리스트를 만들어서 비교했다.

채점 시간이 꽤 걸리길래 처음엔 틀린줄알았는데 브루트포스라 그런거였다.

 

import sys
from itertools import combinations

N = int(sys.stdin.readline().strip())
arr = []

#  N * N 배열로 인풋받기
for _ in range(N):
    arr.append(list(map(int, sys.stdin.readline().split(" "))))

#  i < j인 경우 (상단 삼각형)만 arr[i][j], arr[j][i] 두 값의 합으로 바꿔주기
for i in range(N):
    for j in range(N):
        if i < j:
            arr[i][j] = arr[i][j] + arr[j][i]

result = 100
for one in combinations(range(N), N//2):
    # 이 조합에 없는애들 리스트 만들기
    leftarr = [i for i in range(N)]
    for k in one:
        leftarr.remove(k)

    right = 0
    left = 0
    
    # 각 조합별 능력치의 합
    for com in combinations(one, 2):
        right += arr[com[0]][com[1]]

    for com in combinations(leftarr, 2):
        left += arr[com[0]][com[1]]

    # 절대값으로 차이 구하기
    dif = abs(right - left)
    if dif < result:
        result = dif

print(result)

 

 

 

시간이 너무 오래걸려서 가지치기를 했다. 

A그룹이 (1,2,3) + B그룹이 (4,5,6)인 경우와

A그룹이 (4,5,6) + B그룹이 (1,2,3)인 경우가 같으니까

조합으로 나온애들의 앞 반개만 돌리면 결과는 같고 시간이 반으로 줄어든다!

# 14889 스타트와 링크

import sys
from itertools import combinations

N = int(sys.stdin.readline().strip())
arr = []

#  N * N 배열로 인풋받기
for _ in range(N):
    arr.append(list(map(int, sys.stdin.readline().split(" "))))

#  i < j인 경우 (상단 삼각형)만 arr[i][j], arr[j][i] 두 값의 합으로 바꿔주기
for i in range(N):
    for j in range(N):
        if i < j:
            arr[i][j] = arr[i][j] + arr[j][i]

result = 100

# 전체 조합 구해서 리스트로 만들기
rawcom = list(combinations(range(N), N // 2))

# 조합 리스트에서 앞 반개만큼만 돌리기 (뒷 반은 어차피 겹치는 상황이니까)
for one in rawcom[:len(rawcom)//2]:
    # 이 조합에 없는애들 리스트 만들기
    leftarr = [i for i in range(N)]
    for k in one:
        leftarr.remove(k)

    right = 0
    left = 0

    # 각 조합별 능력치의 합
    for com in combinations(one, 2):
        right += arr[com[0]][com[1]]

    for com in combinations(leftarr, 2):
        left += arr[com[0]][com[1]]

    # 절대값으로 차이 구하기
    dif = abs(right - left)
    if dif < result:
        result = dif

print(result)