# 문제

• SWEA-2115 : [모의 SW 역량테스트] 벌꿀채취

# 풀이

이번에도 역시 itertools.combinations를 사용하면 쉽게 풀린다.

from itertools import combinations

def isSafe(x, y):
temp = 0
for i in range(M):
# if -1 < x < N and -1 < y+i < N:
if -1 < y+i < N:
temp += 1

return 1 if temp == M else 0

def cal(x, y):
cap = []
for i in range(M):
temp = honey[x][y+i]
cap.append(temp)

subsum = []
for j in range(M):
combs = combinations(cap, M-j)
for comb in combs:
if sum(comb) <= C:
summ = 0
for k in comb:
summ += k**2
subsum.append(summ)

return max(subsum)

def profit(i, j):
prof1 = cal(i, j)

temp = []
for a in range(i, N):
k = j+M if a == i else 0
for b in range(k, N):
if isSafe(a, b):
temp.append(cal(a, b))

return max(temp)+prof1 if temp else 0

T = int(input())
for test_case in range(1, T + 1):

N, M, C = map(int, input().split())

honey = []
for _ in range(N):
honey.append(list(map(int, input().split())))

maxi = 0
for i in range(N):
for j in range(N):
if isSafe(i, j):
maxi = max(maxi, profit(i, j))

print("#%d %d" % (test_case, maxi))