[SWEA] 2115. 벌꿀채취 (Python)

link 🔗 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu 

SW Expert Academy

 

1️⃣ 각각 DFS 돌려주기

 

def dfs(n, cnt, profit, lst):
    global sol
    if n == M:
        if cnt <= C:
            if sol < profit:
                sol = profit
        return
    dfs(n+1, cnt, profit, lst)
    dfs(n+1, cnt+lst[n], profit+lst[n]**2, lst)

t = int(input())

for tc in range(1, t+1):
    N, M, C = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    Max = -1e9
    for y1 in range(N):
        for x1 in range(N-M+1):
            sol = 0
            temp = dfs(0, 0, 0, arr[y1][x1:x1+M]) # 인덱스, 채취한 꿀양, 수익, 선택한 벌통
            ans1 = sol
            for y2 in range(y1, N):
                sx = 0
                if y1 == y2: # y1과 y2가 같은 줄이면
                    sx = x1+M
                for x2 in range(sx, N-M+1):
                    sol = 0
                    dfs(0, 0, 0, arr[y2][x2:x2+M])
                    ans2 = sol
                    Max = max(Max, ans1+ans2)
    print(f'#{tc} {Max}')