[Python/BOJ] 25602. 캔 주기
https://www.acmicpc.net/problem/25602
25602번: 캔 주기
첫째 줄에 $N$, $K$가 주어진다. ($1 \le N \le 5, 1 \le K \le 4$) 둘째 줄에 랑이 집사가 가진 캔의 수를 의미하는 $A$ 배열이 공백으로 구분되어 주어진다. 이 줄의 i번째 값이 $A[i]$ 값이다.$(0 \le A[i] \le 8$,
www.acmicpc.net
문제
랑이 집사는 자신의 고양이 랑이와 메리 둘에게 매일 아침 캔을 정확히 하나씩 준다.
랑이 집사가 가진 캔의 종류는 가지로, 집사는 번째 캔을 개 갖고 있다.
랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. 번째 날 랑이가 번째 캔을 먹었을 때 만족도는 , 번째 날 메리가 번째 캔을 먹었을 때 만족도는 로 나타난다.
자연수 과 , , 배열이 주어질 때, 랑이 집사가 현재 가진 캔으로 일동안 랑이와 메리에게 하루에 하나의 캔을 줘서 얻을 수 있는 만족도의 합의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 , 가 주어진다. (1≤N≤5,1≤M≤4)
둘째 줄에 랑이 집사가 가진 캔의 수를 의미하는 배열이 공백으로 구분되어 주어진다. 이 줄의 i번째 값이 값이다.(0≤A[i]≤8, 모든 캔의 수의 합은 2×K개 이상이다.)
셋째 줄부터 줄에 걸쳐 랑이의 번째 날 번째 캔의 선호도 배열이 주어진다. 이 입력들의 번째 행, 번째 열의 값이 값이다.(1≤R[i][j]≤100)
번째 줄부터 줄에 걸쳐 메리의 번째 날 번째 캔의 선호도 배열이 주어진다. 이 입력들의 번째 행, 번째 열의 값이 값이다.(1≤M[i][j]≤100)
출력
랑이와 메리의 만족도의 합의 최댓값을 출력한다.
풀이
Code
import sys
input = sys.stdin.readline
ans = -int(1e9)
def solution(n, m, array, RANGE, MERRY) :
# 1. 백트래킹 함수 정의
def backtracking(who, i, summation) :
global ans
# 1-1. 종료 조건 설정
if i == m :
# 1-1-1. 랑이인 경우
if who == 'R' :
# 메리 만족도 체크를 위한 백트래킹 실행
backtracking('M', 0, summation)
# 1-1-2. 메리인 경우
else :
# 최댓값 업데이트
ans = max(ans, summation)
return
# 1-2.
for j in range(n) :
# 1-2-1. 캔이 없을 경우 continue
if array[j] == 0 : continue
# 1-2-2. 캔 개수 차감
array[j] -= 1
# 1-2-3. 백트래킹 실행
if who == 'R' : backtracking(who, i+1, summation + RANGE[i][j])
else : backtracking(who, i+1, summation + MERRY[i][j])
# 1-2-4. 캔 개수 증가
array[j] += 1
# 2. 랑이 만족도 체크를 위한 백트래킹 실행
backtracking('R', 0, 0)
# 3. 결과 출력
print(ans)
if __name__ == "__main__":
n, m = map(int, input().split())
array = list(map(int, input().split()))
RANGE = [list(map(int, input().split())) for _ in range(m)]
MERRY = [list(map(int, input().split())) for _ in range(m)]
solution(n, m, array, RANGE, MERRY)