[SWEA] 벌꿀채취

📌 문제 링크

문제 자체는 빨리 풀었는데 테케를 몇 개씩 계속 틀려서 고민했던 문제이다.
별도의 알고리즘은 사용되지 않았고,
combinations 라이브러리를 사용하였다.

풀이 방법)

NxN 벌통이 있을 때, 두 일꾼이 서로 겹치지 않게 꿀을 채집해야한다.
위의 그림에서 가장 오른쪽 경우를 어떻게 처리해야할지 고민했었는데
댓글을 보니 저런 경우는 고려하지 않아도 된다는 말이 있어서
N개의 행에서 2개의 행을 선택할 수 있는 모든 경우의 수를 combinations으로 구하였다.

그런 다음 선택된 행에서 연속된 M개의 숫자를 선택할 수 있는 모든 경우를 이중 for문으로 구하고,
그렇게 뽑은 값들 중에 수익을 구했을 때 최댓값이 나오는 값을 찾는 방식으로 구현했다

변수 이름이나 코드가 다 정리되지 않았지만 제출한(해서 정답이 된) 코드는 다음과 같다.

import sys
from itertools import combinations

sys.stdin = open("bee.txt", "r")

def choice_beehive(a_worker, b_worker):
    global N, M, max_income

    # 2개의 열에서 각자 연달아 M개 벌통을 선택할 수 있는 모든 경우
    for i in range(0, N-M+1):
        for j in range(0, N-M+1):
            income = collection_honey(a_worker[i:i+M]) + collection_honey(b_worker[j:j+M])
            if income > max_income:
                max_income = income
            
def collection_honey(beehive):
    global C, test_case
        
    collection = []
    max = 0
    
    for k in range(1, len(beehive)+1):
        candi = list(combinations(beehive, k))
        for c in candi:
            if sum(c) <= C:
                collection.append(c)

    for s in collection:
        income = 0
        for p in s:
            income += pow(p, 2)
        if income > max: 
            max = income
        
    return max


T = int(input())
for test_case in range(1, T + 1):
    max_income = 0
    beehive = []

    N, M, C = map(int, input().split()) # 벌통 크기, 선택 벌통 개수, 채취 최대 양
    colomn = [ele for ele in range(N)]
    
    # NxN 벌통 만들기
    for _ in range(N):
        beehive.append(list(map(int, input().split())))

    # N 열 중 2개 선택
    for a, b in combinations(colomn, 2):
        choice_beehive(beehive[a], beehive[b])

    print(f"#{test_case} {max_income}")

이중 for문을 굉장히 많이 돌게 되어서 아쉬운 마음이 있다..🥲

헤맸던 부분)

처음에 구현했던 코드는 이런 경우 7+2+9가 C 값인 10보다 크므로 9를 제외한 7과 2만 선택하는 방식이었다.
하지만 위의 상황처럼 수익이 최대가 되려고 했을 때, 벌꿀을 한칸만 채취하거나 두 칸만 채취하거나 하는 경우도 모두 고려해야한다는 것을 알았다.

for k in range(1, len(beehive)+1):
        candi = list(combinations(beehive, k))
        for c in candi:
            if sum(c) <= C:
                collection.append(c)

그래서 선택한 행에서 선택할 수 있는 모든 경우를 collection이라는 list에 append 하고
collection 안을 돌면서 가장 큰 수익을 내는 짝을 찾는 방식으로 구현하였다.

끝.