[코딩테스트][SWEA] 🔥 SWEA 2115번 "벌꿀채취" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 60분

from itertools import combinations

for tc in range(1,int(input())+1):
    N,M,C=map(int,input().split())
    answer=0
    board=[list(map(int,input().split())) for _ in range(N)]
    for x1 in range(N):
        for y1 in range(N):
            for x2 in range(N):
                for y2 in range(N):
                    group1=set()
                    group2=set()
                    outOfBound=False
                    for m in range(M):
                        if y1+m<0 or y1+m>=N or y2+m<0 or y2+m>=N:
                            outOfBound=True
                            break
                        group1.add((x1,y1+m))
                        group2.add((x2,y2+m))
                    if outOfBound:
                        continue
                    if len(group1&group2)>0:
                        continue
                    group1=[board[x][y] for x,y in list(group1)]
                    group2=[board[x][y] for x,y in list(group2)]
                    maxValue1=0
                    maxValue2=0
                    for i in range(1,M+1):
                        for case in list(combinations(group1,i)):
                            if sum(case)>C:
                                continue
                            sum1=0
                            for k in case:
                                sum1+=k*k
                            maxValue1=max(maxValue1,sum1)
                    for i in range(1,M+1):
                        for case in list(combinations(group2,i)):
                            if sum(case)>C:
                                continue
                            sum2=0
                            for k in case:
                                sum2+=k*k
                            maxValue2=max(maxValue2,sum2)
                    answer=max(answer,maxValue1+maxValue2)
    print("#"+str(tc)+" "+str(answer))                              

벌꿀 채취의 비밀: 완전탐색으로 최대 수익을 찾아라! 🍯

벌꿀을 채취하는 모든 상황을 완전탐색, 즉 브루트포스로 탐색하여 구해내는 문제이다. 먼저 각 M의 길이의 벌통을 각 2명의 일꾼이 선택해야 하므로 이를 for문을 4중으로 써서 간단히 좌표를 구해줄 수 있다. 이 때, 최대 길이가 10이기 때문에 4중 for문을 사용하여도 10,000밖에 되지 않아서 충분히 가능하다.

이 좌표에 대해서 해당 벌통의 좌표를 두개의 그룹으로 구해주면 된다. 이러한 좌표가 현재 NxN의 board를 벗어나거나 겹치는 부분이 존재한다면 다음 케이스로 넘어가주면 된다. 겹치는 부분 존재는 set로 간단히 확인할 수 있으며, board 경계를 통해 보드를 벗어나는지 확인할 수 있다.

벌통을 놓을 수 있다면 여기에서 C가 넘지 않도록 벌통을 선택하는 벌통의 제곱의 합이 최대가 되는 경우를 구하면 된다. 현재 그룹이 2개이므로 현재 그룹에서 벌통을 선택하는 1~M개를 선택하는 모든 조합을 구하고 그 조합에서의 제곱의 합의 최댓값을 각 그룹에 대해서 구하면 된다. 이러한 두 그룹의 최댓값을 더한 값을 통해 정답을 갱신해주면 된다.

이렇게 Python로 SWEA의 "벌꿀채취" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊