greentea31's Note

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

풀이 과정

문제의 조건에 맞게 주어진 벌통을 선택할 때, 선택한 벌통내에서 채취할 수 있는 가치의 최대값을 구하는 문제이다.

일꾼이 벌통을 선택하는 경우를 중복 순열의 경우의 수를 만들어 구하였고, 각 벌통의 칸에서 꿀을 퍼갈지 안퍼갈지를 부분집합의 경우의 수를 만들어 구하였다.

N, M이 크지 않은 수로 주어지므로 완전 탐색으로 풀 수 있음을 추측할 수 있다. 로직을 세우고 시간복잡도를 계산해도 문제에서 주어진 시간을 초과하지 않음을 알 수 있다. 설명은 코드에 주석으로 달아놓았다.

소스 코드

def perm(index):  # 첫번째 벌꿀통의 r, c 두번째 벌꿀통의 r, c를 중복순열로 생성
    if index == 4:
        check()  # 값을 구하러 간다
        return

    for i in range(N):
        numbers.append(i)  # 이번 수를 중복 순열에 넣고
        perm(index+1)  # 다음 index의 수를 고르러 간다
        numbers.pop()  # 이번 수를 중복 순열에 넣지 않고 이번 index에 넣을 다음 수를 찾으러 간다


def check():
    global answer, max1
    a, b, c, d = numbers[0], numbers[1], numbers[2], numbers[3]
    if b > N-M or d > N-M:  # M칸 크기의 벌꿀 통을 가로줄에 넣을 수 없는 경우 진행하지 않는다
        return
    selected = [[False for _ in range(N)] for _ in range(N)]  # 벌꿀통이 놓인 곳을 표시
    subset_selected = [[False for _ in range(N)] for _ in range(N)]  # 벌꿀통 안에서 벌꿀을 퍼갈 공간 표시
    for i in range(M):
        selected[a][b+i] = True  # 벌꿀통을 놓았다고 표시한다
    max1 = 0
    subset(a, b, 0, subset_selected)  # 벌꿀통 안에서 퍼간 벌꿀의 양이 C를 넘지 않으면서 최대 가치를 지니는 경우가 언제인지
    # 부분집합으로 모든 경우를 만들어서 판단한다
    max2 = max1

    for i in range(M):
        if selected[c][d+i]:  # 2번째 벌꿀 통을 놓는데 1번째 벌꿀 통이랑 겹치면 진행하지 않는다
            return
        selected[c][d+i] = True
    max1 = 0
    subset(c, d, 0, subset_selected)  # 2번째 벌꿀 통 안에서 1번째 벌꿀통 부분집합 만들기에서 했던 것과 동일 행위 진행

    answer = max(answer, max1 + max2)  # 정답 갱신


def subset(i, j, index, subset_selected):  # 부분집합 경우의 수 생성 코드
    global max1
    if index == M:  # 모든 벌꿀통의 칸에 대해 진행했으면
        temp = 0
        values = 0
        for k in range(M):
            if subset_selected[i][j+k]:  # 선택된 칸의
                temp += board[i][j+k]  # 양의 누적을 저장하고
                values += board[i][j+k]**2  # 가치의 누적을 저장한다
        if temp > C:  # 양이 C를 넘었으면 담을 수 없으므로 진행하지 않는다
            return
        max1 = max(max1, values)  # 양이 C를 넘지 않았다면 가치 누적값의 최대를 갱신한다
        return

    subset_selected[i][j + index] = True  # 벌꿀통의 특정 칸을 고르는 경우
    subset(i, j, index+1, subset_selected)  # 재귀 진행
    subset_selected[i][j+index] = False  # 벌꿀통의 특정 칸을 고르지 않는 경우
    subset(i, j, index + 1, subset_selected)  # 재귀 진행


T = int(input())

for tc in range(1, T+1):
    max1 = 0
    N, M, C = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]  # 2차원 배열 1줄로 받는 코드
    answer = 0  # 정답을 저장할 변수
    numbers = []  # 중복순열을 생성할 코드
    perm(0)  # 중복순열 재귀
    print(f"#{tc} {answer}")  # 정답 출력