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

문제

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

---

문제 요약

랑이 집사는 매일 고양이 랑이와 메리에게 캔을 하나씩 준다.

 

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

 

랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다.

 

랑이가 i번째날 j번째 캔을 먹었을 때, 만족도는 R[i][j]이다.

 

메리가 i번째날 j번째 캔을 먹었을 때, 만족도는 M[i][j]이다.

 

K일 동안, 랑이와 메리에게 캔을 주었을 때, 만족도 합의 최대를 출력한다.

 

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>

#define ll long long

using namespace std;

int N, K;

// A[i]: i번째 캔 개수
int A[10];

// R[i][j]:랑이가 i번째 날에 j번째 캔을 먹었을 때 만족도
int R[10][10]; 

// M[i][j]:메리가 i번째 날에 j번째 캔을 먹었을 때 만족도
int M[10][10];

int res;

void dfs(int day, int range, int mery) {
    if (day == K + 1) {
        res = max(res, range + mery);
        return;
    }

    // day번째 날의 랑이가 먹을 캔 선택
    for (int i = 1; i <= N; i++) {
        // i번째 캔이 더 이상 없을 경우
        if (A[i] == 0) continue;
        A[i]--;
        
        // day번째 날의 메리가 먹을 캔 선택
        for (int j = 1; j <= N; j++) {
            // j번째 캔이 더 이상 없을 경우
            if (A[j] == 0) continue;
            A[j]--;

            dfs(day + 1, range + R[day][i], mery + M[day][j]);

            A[j]++;
        }

        A[i]++;
    }
}

int main() {
    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> R[i][j];
        }
    }

    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> M[i][j];
        }
    }

    // 1번째 날부터 가능한 경우의수 완전탐색(백트래킹)
    dfs(1, 0, 0);

    cout << res;

    return 0;
}

---

코드 설명

1. 입력  자연수 N, K와 배열 A, R, M을 입력 받는다.

 

2. 1번째 날부터 K번째 날까지 랑이와 메리에게 줄 수 있는 경우의 수를 완전탐색(백트래킹)한다.

 

3. dfs 함수는 랑이와 메리의 day - 1번째 날까지의 만족도를 인자로 받아, day번째 날의 가능한 모든 만족도를 탐색한다.

 

4. 진행 중, 캔의 개수를 -1과 +1 연산을 하면서 탐색한다.

---

고찰

계속해서 느끼는 거지만, 백트래킹 함수의 종료 조건과 인자로 무엇을 넣어야 할 지가 꽤나 어려운 것 같다.

 

문제를 더 많이 풀어야 겠다.