[모의 SW 역량 테스트] 2115 벌꿀 채취 (Python)

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE

문제

N*N 개의 벌통이 정사각형 모양으로 배치되어 있다.

각 칸의 숫자는 각각의 벌통에 있는 꿀의 양을 나타내며, 꿀의 양은 서로 다를 수 있다.

아래 [Fig. 1]은 N=4인 16개의 벌통을 나타낸다.

 

각 벌통에 있는 꿀의 양이 주어졌을 때, 다음과 같은 과정으로 벌꿀을 채취하여 최대한 많은 수익을 얻으려고 한다.

   ① 두 명의 일꾼이 있다. 꿀을 채취할 수 있는 벌통의 수 M이 주어질 때, 
       각각의 일꾼은 가로로 연속되도록 M개의 벌통을 선택하고, 선택한 벌통에서 꿀을 채취할 수 있다.
       단, 두 명의 일꾼이 선택한 벌통은 서로 겹치면 안 된다. 

       아래 [Fig. 2]는 M=2일 때, 두 일꾼이 각각 벌통을 선택하는 다양한 예를 보여준다.
 

 

   ② 두 명의 일꾼은 선택한 벌통에서 꿀을 채취하여 용기에 담아야 한다.
       단, 서로 다른 벌통에서 채취한 꿀이 섞이게 되면 상품가치가 떨이지게 되므로, 하나의 벌통에서 채취한 꿀은 하나의 용기에 담아야 한다.
       하나의 벌통에서 꿀을 채취할 때, 일부분만 채취할 수 없고 벌통에 있는 모든 꿀을 한번에 채취해야 한다.
       두 일꾼이 채취할 수 있는 꿀의 최대 양은 C 이다.


예를 들어, 아래 [Fig. 3]에서 C=10이고, 두 명의 일꾼이 선택한 벌통이 그림과 같을 때,

첫 번째 일꾼은 꿀의 양이 6과 1인 두 개의 벌통에서 모두 꿀을 채취할 수 있다.

하지만 두 번째 일꾼은 꿀의 양이 8과 5인 두 개의 벌통에서 모두 꿀을 채취할 경우,

채취한 꿀의 양이 13이 되어 C=10을 초과하기 때문에 두 개의 벌통에서 모두 꿀을 채취할 수 없다.

따라서 두 번째 일꾼은 꿀의 양이 8과 5인 벌통 중 하나를 선택하여 꿀을 채취해야 한다.

[Fig. 3]은 그 중 한 예를 보여주고 있다.

 

 

   ③ 채취한 꿀은 시장에서 팔리게 된다. 이때 하나의 용기에 있는 꿀의 양이 많을수록 상품가치가 높아, 각 용기에 있는 꿀의 양의 제곱만큼의 수익이 생긴다.
       예를 들어 위 [Fig. 3]과 같이 꿀을 채취할 경우, 꿀의 양이 6, 1, 8인 세 개의 용기가 얻어지며 이때 수익의 합은, (6*6) + (1*1) + (8*8) = 36 + 1 + 64 = 101 이 된다.


벌통들의 크기 N과 벌통에 있는 꿀의 양에 대한 정보, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 주어진다.

이때 두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대가 되는 경우를 찾고, 그 때의 최대 수익을 출력하는 프로그램을 작성하라.


[예시 1]

벌통들의 크기 N=4, 선택할 수 있는 벌통의 개수 M=2, 채취할 수 있는 꿀의 최대 양 C=13 이고,

아래 [Fig. 4]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.

최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 4]와 같이 벌통을 선택하여 선택하여 꿀을 채취하게 되면, 총 수익이 174가 되어 최대가 된다.

따라서 이 경우 정답은 174이다.

 

 

[예시 2]

벌통의 크기 N=3, 선택할 수 있는 벌통의 개수 M=3, 채취할 수 있는 꿀의 최대 양 C=10 이고,

아래 [Fig. 5]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.

최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 5]와 같이 벌통을 선택하여 꿀을 채취하게 되면, 총 수익이 131이 되어 최대가 된다.

따라서 이 경우 정답은 131이다.

 

 

[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초.

2. 벌통들의 크기 N은 3 이상 10 이하의 정수이다. (3 ≤ N ≤ 10)

3. 선택할 수 있는 벌통의 개수 M은 1 이상 5 이하의 정수이다. (1 ≤ M ≤ 5)

4. 선택할 수 있는 벌통의 개수 M은 반드시 N 이하로만 주어진다.

5. 꿀을 채취할 수 있는 최대 양 C는 10 이상 30 이하의 정수이다. (10 ≤ C ≤ 30)

6. 하나의 벌통에서 채취할 수 있는 꿀의 양은 1 이상 9 이하의 정수이다.

7. 하나의 벌통에서 일부분의 꿀만 채취할 수 없고, 벌통에 있는 모든 꿀을 한번에 채취해야 한다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 벌통들의 크기 N, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 차례로 주어진다.

그 다음 줄부터 N*N 개의 벌통에서 채취할 수 있는 꿀의 양에 대한 정보가 주어진다.


[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 두 일꾼이 꿀을 채취하여 얻을 수 있는 최대 수익이다.

 

10  4 2 13 6 1 9 7     9 8 5 8 3 4 5 3 8 2 6 7 3 3 10 7 2 9 6 6 6 5 5 7 …

#1 174 #2 131 #3 145 #4 155 #5 166 #6 239 #7 166 #8 172 #9 291 #10 464

 

풀이

재귀를 활용해 부분집합을 구하여 문제를 해결하였다. 

고려해야할 점은 

첫 째, 꿀통의 조합( 첫 번째 사람의 꿀통의 위치, 두 번째 사람의 꿀통의 위치)

둘 째, 꿀의 최대양을 고려한 꿀통의 부분집합을 구하여 이득을 계산하는 것.

이 두가지를 구현하면 해결되는 문제이다.

첫 번째 꿀통의 조합 같은 경우에는 반복문을 통하여 완전 탐색을 실시하였다. 첫 번째 사람과 두 번째 사람의 꿀 통 조합을 만들어 내면 그 이후에는 재귀를 활용해 부분집합을 구하였다. 중간에 계산값이 최대양을 넘어서게 되면 가지치기를 하여 조금이라도 최적화를 시키려고 했지만 애초에 데이터 양이 그렇게 많진 않아서 미비할 것이라 생각된다.

첫 번째 사람의 부분집합, 두 번째 사람의 부분집합을 구하고 이를 profit 함수를 통해 최대치를 뽑아내어 이득값을 계산함으로서 문제를 해결할 수 있었다.

코드

def profit(array1, array2): # 이득계산
    global max_honey
    global answer
    answer = []
    bubun(0,array1,0,0)
    max1 = max(answer)
    answer = []
    bubun(0,array2,0,0)
    max2 = max(answer)
    if max1 + max2 > max_honey:
        max_honey = max1+max2
    return 
 
def number2(row,col):
    arr2 = []
    if col+2*M-1 < N: # 2번 벌꿀통이 1번과 같은 행에 존재하는지 확인
        for i in range(M):
            arr2.append(honey[row][col+M+i]) # 2번 사람 벌꿀통
 
    profit(arr1,arr2) # 같은 행에 존재하면 이득 계산
    
    for rows in range(row+1,N): #그 다음행부터 M칸 만큼씩 전부 타맥
        for col in range(N):
            if col+M-1 < N:
                arr2 = []
                for i in range(M):
                    arr2.append(honey[rows][col+i])
                    profit(arr1,arr2)
 
def bubun(idx,a,summ,result): # 부분집합 만드는 부분
    if summ > C: # 가지치기
        return
    if idx == len(a) and summ <= C:
        answer.append(result)
        return 
    bubun(idx+1,a,summ+a[idx],result+a[idx]**2)
    bubun(idx+1,a,summ,result)
 
T = int(input())
for t in range(T):
    N, M, C = map(int,input().split()) # N = 맵크기 / M = 벌통 개수 / C  = 꿀 최대양
    honey = [list(map(int,input().split())) for _ in range(N)]
    max_honey = -9999999
    for x in range(N-1):
        for y in range(N): # 열을 한칸 씩 민다
            if y+M-1 < N: # 현재 열에서 M만큼 더한 위치가 맵 범위 안이면 벌꿀 채취가능
                arr1 = []
                for i in range(M): 
                    arr1.append(honey[x][y+i]) # 1번 사람 벌꿀통
                    number2(x,y) # 2번 사람 벌꿀통 찾으러들어감
    print('#{} {}'.format(t+1,max_honey))

 

회고

이번 문제도 마음에 들지 않는다. 특히 profit 함수가 정말 마음에 안든다. 구현능력이 아직 부족해서 저렇게 똑같은 내용을 반복해서 적을 수 밖에 없었는데 다른 구현 문제들을 좀더 다루어 보고 다시 좀 더 깔끔하게 풀어봐야겠다.