[BOJ/Silver 1] 백준 25602 캔 주기(C++)

문제 링크

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 × 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)

출력

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

예제 입력 1

5 3
2 1 3 1 5
1 2 3 4 5
5 4 3 2 1
1 2 1 2 1
10 10 10 10 10
3 3 3 3 3
3 2 1 5 4

예제 출력 1

30

알고리즘 분류

• 백트래킹

풀이

캔이 종류 구분 없이 최대 40개까지 존재할 수 있다. 따라서 1일차부터 최대 4일차까지 랑이와 메리에게 어떤 캔을 줄 것인지를 완전 탐색해도 시간이 초과되지 않는다.

랑이에게 특정 캔을 주었다고 가정하면 해당 캔의 개수를 1 줄이고, 바로 메리에게 준 캔의 개수를 1 줄이고 재귀를 통해 다음 날로 넘어간다.

K일차가 넘으면 랑이와 메리의 만족도의 합의 최댓값을 갱신한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 6
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K;
int A[MAX];
int R[MAX][MAX], M[MAX][MAX];
int Answer;

void input() {
    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];
        }
    }
}

void DFS(int Day, int Rang, int Mary) {
    if (Day > K) {
        Answer = max(Answer, Rang + Mary);
        return;
    }

    for (int i = 1; i <= N; i++) {
        int NewRang = Rang;
        int NewMary = Mary;
        if (A[i] > 0) {
            A[i]--;
            NewRang += R[Day][i];
            for (int j = 1; j <= N; j++) {
                if (A[j] > 0) {
                    A[j]--;
                    NewMary += M[Day][j];
                    DFS(Day + 1, NewRang, NewMary);
                    NewMary -= M[Day][j];
                    A[j]++;
                }
            }
            NewRang -= R[Day][i];
            A[i]++;
        }
    }
}

void settings() {
    DFS(1, 0, 0);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}