[BOJ/백준] 15661 링크와 스타트

import sys
from itertools import combinations
def input():
    return sys.stdin.readline().rstrip()


N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]
row = [sum(i) for i in arr]
col = [sum(i) for i in zip(*arr)]
new_arr = [i+ j for i, j in zip(row, col)]
total_sum = sum(new_arr)//2
result = float('inf')
for num in range(1,N//2+1):
    for combi in combinations(new_arr,num):
        result = min(result,abs(total_sum-sum(combi)))
        if result == 0:
            break
    if result == 0:
        break
print(result)

이 문제는 과거에 푼 boj.kr/14889 이 있었기 때문에 빨리 풀 수 있었다. 

 

기본 푼 방식은 원래와 똑같다. 각 col,row의 섬을 미리 구해놓고, 그걸 통해서 문제를 푸는 방식이다.