SW Expert Academy - 벌꿀 채취 (python)

❓ 문제 - SW Expert Academy 벌꿀 채취 python 풀이법

 

출처 

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

 

 

 

📝 문제해결법

1. 이 문제는 DFS 2번+ 구현으로 풀었다.

• 한사람이 벌꿀채취를 할 때 가로열의 맨 처음 인덱스는 (0 ~ n-m-1)까지 가능하므로 모든 행과 해당 열에 맞춰 두 사람에 대한 조합을 으로 두 사람이 벌꿀채취를 할 수 있는 경우의 수를 다 뽑는다.
• 다음으로 두 사람에 대해 만약 같은 행인데, 두 사람이 벌꿀재취를 할 때 가로의 맨 처음 인덱스의 차이가 m 보다 작으면 둘이 겹치므로 해당 경우는 탐색하지 않고, 그 외의 경우에는 solve1()함수를 통해 꿀을 채취했을 때 얻을 수 있는 금액의 최대값을 갱신한다.
• solve1() 함수에서 만약 벌꿀채취를 하려는 가로열의 합이 c보다 크다면 m개의 가로열중 최대 이윤을 남기는 일부만 채취할 수 있으므로 최대 이윤을 구하기 위해 solve2() 함수로 DFS를 돌린다.
• solve2() 함수에는 현재까지 꿀을 채취한 양 summ, 현재까지 꿀을 채취한 양의 제곱의 합 result를 이용하는데 우선 summ이 c보다 크면 dfs 순회를 종료하고, 만약 마지막까지 열까지 순회를 했는데도 summ이 c보다 작다면 result인 이윤을 비교할 리스트에 넣어준다. 이외엔, 해당 열을 선택했을 때의 summ과 result 값으로  dfs를 돌리고, 해당 열을 선택하지 않았을 때 summ과 result 값으로 dfs를 돌린다.
• 만약 벌꿀재취를 하려는 가료열의 합이 c보다 커서 solve2() 함수를 돌렸으면, 최대 이윤을 찾기위해 이윤들을 담은 리스트의 최대값을 한 사람의 최대이윤으로 선택해 더해준다.

2. 문제 풀면서 느낀점

• 처음에 가로열의 합이 c보다 큰 경우, 내림차순해서 계속 더하면서 만약 c보다 더 크면 그 직전까지 제곱의 값을 더해서 최대이윤으로 정했는데, 그럼 7, 5, 5 에서 c=10일 때는 7^2 = 49로 최대이윤을 구하게되는데 , 사실 (5^2 + 5^2) = 50이 더 크므로 이 방법은 틀렸다. 따라서 DFS로 다시 최대이윤을 구할 수 있게 다른 사람의 코드를 참고해서 구현했다...
• DFS + DFS 문제라니 ... 이런 문제도 접할 수 있어서 좋은 경험이었다. 다음에 이런 사소한 부분까지 잘 구현할 줄 아는 사람이 되자 !!

 

💻 소스코드

T = int(input())
def solve2(idx, a, summ, result):
    if summ > c:
        return
    if idx == len(a) and summ <= c:
        alst.append(result)
        return
    solve2(idx+1, a, summ+a[idx], result+a[idx]**2)
    solve2(idx+1, a, summ, result)

def solve(c1, c2):
    arr1 = []
    arr2 = []
    money = 0
    global alst
    for j in range(m):
        arr1.append(board[c1[0]][c1[1]+j])
        arr2.append(board[c2[0]][c2[1]+j])
    if sum(arr1) > c:
        alst = []
        solve2(0, arr1, 0, 0)
        money += (max(alst))
    else:
        for a in arr1:
            money += (a*a)

    if sum(arr2) > c:
        alst = []
        solve2(0, arr2, 0, 0)
        money += (max(alst))
    else:
        for a in arr2:
            money += (a * a)
    return money

def combination(lst, num):
    result = []
    if num > len(lst):
        return result
    if num == 1:
        for l in lst:
            result.append([l])
    elif num > 1:
        for i in range(len(lst)-num+1):
            for temp in combination(lst[i+1:], num-1):
                result.append([lst[i]]+temp)
    return result

for test_case in range(1, T+1):
    n, m, c = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    c_lst = []
    for i in range(n):
        for j in range(n):
            if j+(m-1) > n-1:
                break
            c_lst.append([i, j])
    answer = -1

    for com in list(combination(c_lst, 2)):
        if com[0][0] == com[1][0] and abs(com[0][1]-com[1][1]) < m:
            continue
        answer = max(answer, solve(com[0], com[1]))
    print(f'#{test_case} {answer}')