문제

• 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))