[백준] 25602번 : 캔 주기 (C++)

25602번 : 캔 주기

---

문제)

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

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

 

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

 

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

 

 

 

 

입력 :

 

 

 

출력 :

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

 

 

 

 

 

 

 

풀이)

// 25602. 캔 주기
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, k;
vector<int> can;
vector<vector<int>> rang;
vector<vector<int>> me;
 
vector<int> vec;
vector<int> arr;
 
int ans = 0;
void recur(int cur)
{
    if (cur == k)
    {
        int result = 0;
        for (int i = 0; i < k; i++)
        {
            result += rang[i][vec[i]];
        }
 
        for (int i = 0; i < k; i++)
        {
            result += me[i][arr[i]];
        }
 
        ans = max(ans, result);
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (can[i] == 0) continue;
        vec[cur] = i;
        can[i]--;
 
        for (int j = 0; j < n; j++)
        {
            if (can[j] == 0) continue;
            arr[cur] = j;
            can[j]--;
            recur(cur + 1);
            can[j]++;
        }
        can[i]++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
    can.resize(n);
    vec.resize(n);
    arr.resize(n);
    for (int& ele : can) cin >> ele;
 
    rang.resize(k, vector<int>(n));
    me.resize(k, vector<int>(n));
    
    for (auto& ele : rang) for (int& e : ele) cin >> e;
    for (auto& ele : me) for (int& e : ele) cin >> e;
 
    recur(0);
 
    cout << ans;
 
    return 0;
}
 

---

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

25602번: 캔 주기