[백준/Python] 25602번 캔 주기

https://www.acmicpc.net/problem/25602

---

문제

랑이 집사는 자신의 고양이 랑이와 메리 둘에게 매일 아침 캔을 정확히 하나씩 준다.

랑이 집사가 가진 캔의 종류는 N가지로, 집사는 i번째 캔을 A[i]개 갖고 있다.

랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. 
i번째 날 랑이가 j번째 캔을 먹었을 때 만족도는 R[i][j], 
i번째 날 메리가 j번째 캔을 먹었을 때 만족도는 M[i][j]로 나타난다.

자연수 N과 A, R, M 배열이 주어질 때, 랑이 집사가 현재 가진 캔으로 
K일동안 랑이와 메리에게 하루에 하나의 캔을 줘서 얻을 수 있는 만족도의 합의 최댓값을 구하는 프로그램을 작성하시오.

---

입력 & 출력

첫째 줄에 N, K가 주어진다. (1 <= N <= 5, 1 <= K <= 4)

둘째 줄에 랑이 집사가 가진 캔의 수를 의미하는 A 배열이 공백으로 구분되어 주어진다. 이 줄의 i번째 값이 A[i] 값이다.
(0 <= A[i] <= 8, 모든 캔의 수의 합은 2 X K개 이상이다.) 

셋째 줄부터 K줄에 걸쳐 랑이의 i번째 날 j번째 캔의 선호도 R 배열이 주어진다. 이 입력들의 i번째 행, j번째 열의 값이 R[i][j] 값이다. (1 <= R[i][j] <= 100) 

K + 3번째 줄부터 K줄에 걸쳐 메리의 i번째 날 j번째 캔의 선호도 M 배열이 주어진다. 이 입력들의 i번째 행, j번째 열의 값이 M[i][j] 값이다.
(1 <= M[i][j] <= 100)

랑이와 메리의 만족도의 합의 최댓값을 출력한다.

 

---

코드

input = __import__('sys').stdin.readline

N, K = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))
Rang = []
Mery = []
flavor_max = 0

for i in range(K) :
    Rang.append(list(map(int, input().rstrip().split())))
for i in range(K) :
    Mery.append(list(map(int, input().rstrip().split())))

def Feed(day, flavor) :
    global flavor_max

    if day == K :
        if flavor > flavor_max :
            flavor_max = flavor
        return 

    for i in range(N) :
        if A[i] > 0 :
            A[i] -= 1
        else :
            continue
        for j in range(N) :
            if A[j] > 0 :
                A[j] -= 1
                Feed(day + 1, flavor + Rang[day][i] + Mery[day][j])
            else :
                continue
            A[j] += 1
        A[i] += 1

Feed(0, 0)
print(flavor_max)

 

풀이

완전탐색 (백트랙킹)을 이용하여 풀이를 진행했다.  1일차에 랑이에게 줄 i 번째, 메리에게 줄 j 번쨰 캔이 있다면 선호도를 더한 뒤, 다음 날 다시 반복하며 탐색을 진행했다. 마지막 날(K)에 도달한 경우, 최대 선호도 값과 비교하여 최대 선호도 값을 찾는다.
처음 백트랙킹을 접했을 때는 어디서부터 무엇을 기준으로 탐색을 진행하여야 할지, 어떤 변수를 이용해서 언제 리턴을 해야할 지 고민을 많이 하였다. 문제를 풀기 전 먼저, 특정한 날자를 기준으로 잡고, 남아있는 캔들을 탐색해가며 반복해야 한다고 생각하고 알고리즘을 생각해려 하니, 수월하게 풀 수 있었다.