[백준 28447번] 파이썬 - 마라탕 재료 고르기

백준 28447 - 마라탕 재료 고르기

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 하얔이는 마라탕에 여러 재료를 넣어 먹는 것을 좋아한다.
• 하지만 마라탕에 항상 많은 재료를 넣는다고 맛있는 것은 아니다.
• 마라탕은 각 재료마다 궁합이 존재해서 같이 넣으면 맛있는 재료도 있고 그렇지 않은 경우도 있다. 여기서 하얔이는 고민에 빠졌다.

대체 어떻게 해야 K개의 재료를 넣었을 때 마라탕의 맛을 최대로 할 수 있는거지?

 - C{i, j}를 재료 i와 재료 j를 같이 넣었을 때의 궁합이라 하자.
 - 마라탕의 맛은 마라탕에 들어간 모든 재료 쌍의 궁합의 합이다.
 - 고른 재료의 그룹을 G라고 했을 때 마라탕의 맛을 수식으로 표현하면 다음과 같다.
$$\sum_{i, j\in G,\ i < j}C_{i,j}$$

• 가여운 하얔이를 위해 재료를 K개만 사용했을 때의 최대의 마라탕의 맛을 구해보자.

입력

• 첫째 줄에 마라탕 재료의 수 N(1<=N<=10), 고를 재료의 수 K(1<=K<=N)가 공백으로 주어진다.
• 이후, N개의 줄에 걸쳐 i+1번 줄에 재료 i와 다른 재료들의 궁합을 나타내는 수열 Ci1, Ci2, ... , CiN이 공백으로 구분되어 정수로 주어진다. (-1,000 <= Cij <=1000)
  • 단, (Cii = 0, Cij = Cji)

출력

• 첫째 줄에 K개의 재료만 사용한 마라탕의 맛의 최댓값을 출력한다.

# 접근 방법

• 재료가 10개 밖에 되지 않으므로 K개의 조합을 구해준다.
• 이후 result는 최대한 작은 수로 설정해준 후, 조합에 따른 궁합도를 더해주고 갱신해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  

N, K = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
result = -float('inf')  

for comb in list(combinations(range(N), K)):  
    temp = 0  
    for i in range(K-1):  
        for j in range(i+1, K):  
            temp += arr[comb[i]][comb[j]]  
    if temp > result:  
        result = temp  

print(result)