[백준] 16457번 단풍잎 이야기 C++

문제 : https://www.acmicpc.net/problem/16457

C++

#include<iostream>
#include<algorithm>

using namespace std;

vector<int> Quest[100];
bool visited[100];

int n,m,k,skill,final = 0;

void search(int num, int skills) { // 3개 뽑음
    if(num==n) {
        int total = 0;
        for(int i = 0; i < m; i++) {
            bool check = true;
            for(int j = 0; j < k; j++) {
                if(!visited[Quest[i][j]]) {
                    check = false;
                    break;
                }
            }
            if(check) {
                total++;
            }
        }
        final = max(final, total);
    }

    for(int i = skills; i <= 2 * n; i++) {
        if(!visited[i]) {
            visited[i] = true;
            search(num+1, i+1);
            visited[i] = false;
        }
    }
}

int main() {
    // 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬 수 k
    // m개의 줄 각각의 퀘스트에서 사용해야 해야 하는 스킬
    // 최적의 키배치 햇을 때 최대로 깰 수 있는 퀘스트의 개수
    // 2n개의 스킬 중 n개를 적절히 키에 배치
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < k; j++) { // 각 퀘스트 별로 skill 두 개씩 넣음
            cin >> skill;
            Quest[i].push_back(skill);
        }
    }

    search(0,1);
    cout << final;

}

문제풀이

• 2n개의 스킬 중에서 n개의 스킬을 뽑아 해결할 수 있는 최대 퀘스트를 구해야한다. 그리고 각 퀘스트당 k개의 스킬이 필요하기 때문에 각 퀘스트에 해당하는 스킬을 입력하기 위해 vector를 사용했다. 이후 DFS 방법을 사용해서 2n개의 스킬 중 n개의 스킬을 뽑는 모든 경우의 수에 대한 최댓값을 비교했다.

Comment

• 초반에 예제와 문제를 제대로 이해하지 못해서 어려움을 겪었다... 문제를 열심히 읽자. 문해력을 키우자. 메모,,