[Python] SW Expert Academy #2115 벌꿀채취

📚문제: #2115 벌꿀채취(모의 SW 역량테스트)

전체 코드

# 2115. 벌꿀채취

from copy import deepcopy
from itertools import combinations

# 최대 이익 함수
def max_profit(G, t):
    
    # 채취 가능 영역
    region = []
    
    # 최대 수익 초기화
    max_ans = -1
    
    # 영역 선택
    for i in range(N):
        
        for j in range(N):
            
            # 영역을 벗어나지 않을 때만 가능 영역에 추가
            if j+M <= N:
                
                temp = []
                
                for k in range(M):
                    
                    temp.append([i,j+k])
                    
                region.append(temp)
    
    # 두 개의 영역
    A = deepcopy(region)
    B = deepcopy(region)
    
    for i in range(len(A)):
        
        for j in range(len(B)):
            
            if i == j:
                
                continue
            
            else:
                
                array = []
                
                for coord in A[i]:
                    
                    array.append(coord)
                
                for coord in B[j]:
                    
                    array.append(coord)
                
                # 중복 제거
                array = list(set(tuple(x) for x in array))
                
                # 겹치는 영역이 없을 때 계산 실행
                if len(array) == 2 * M:
                
                    reg_A = A[i]
                    reg_B = B[j]
                    
                    # 벌꿀 채취
                    max_A = max_collection(reg_A)
                    max_B = max_collection(reg_B)
                    
                    # 최대 가격 갱신
                    max_ans = max(max_ans, max_A + max_B)
    
    # 정답 출력
    print("#{} {}".format(t, max_ans))
                    
# 벌꿀 채취 및 최대 수익 계산 
def max_collection(G):
    
    # 최대 수익 초기화
    max_val = -1
    
    all_combs = []
    
    G = list(tuple(x) for x in G)
    
    for i in range(1, len(G)+1):
        
        combs = list(combinations(G, i))
        
        for comb in combs:
            
            all_combs.append(comb)
    
    for comb in all_combs:
        
        total_C = 0
        total_Square = 0
        
        for coord in comb:
            
            r, c = coord
            
            total_C += box[r][c]
            total_Square += box[r][c]**2
        
        # C이하일 때만 계산 가능
        if total_C <= C:
            
            max_val = max(max_val, total_Square)
    
    return max_val

# 테스트 케이스 T
T = int(input())

# T개의 테스트 케이스가 주어진다.
for t in range(1, T+1):
    
    # 벌통 크기 N, 벌통 개수 M, 최대 채취 양 C
    N, M, C = map(int, input().split())
    
    # 벌통
    box = []
    
    # N x N개의 벌통에서 채취 가능한 꿀의 양이 주어진다.
    for _ in range(N):
        
        box.append(list(map(int, input().split())))
    
    # 함수 실행
    max_profit(box, t)

아이디어 및 로직

1. N × N 벌통에서 M개를 가로(연속)로 선택하는 경우를 모두 구한다.
2. 두 개의 영역이 겹칠 때는 Skip, 겹치지 않을 때는 각각의 영역에서 최대 수익 계산 로직으로 들어간다.
3. 벌통의 개수를 1,2,3 ~ M개 선택하는 모든 조합을 구한 후 각 조합의 벌꿀 채취 합이 C이하인지, 초과인지 계산한다.
4. C이하이면 수익을 계산 후 최대 수익 값 갱신, C초과면 해당 케이스는 Skip한다.