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

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

16457번: 단풍잎 이야기

 

 

어떤 문제인가?

 

m개의 퀘스트가 존재한다. 각 퀘스트는 k개의 스킬을 써서 완료할 수 있다.

1부터 2*n까지의 정수 중 n개를 뽑는다.

이때의 정수가 퀘스트를 완료할 때 필요한 스킬이다.

이때 퀘스트를 가장 많이 완료할 수 있는 경우를 찾으면 된다.

 

 

접근 방법

int n, m, k;
int quest[101][10];

 

문제에서 주어진 변수와 입력된 퀘스트를 저장할 2차원 배열을 선언해줬다.

 

cin >> n >> m >> k;

for (int i = 0; i < m; i++) {
    for (int j = 0; j < k; j++) {
        cin >> quest[i][j];
    }
}

문제의 조건에 맞게 입력받아준다.

 

 

먼저 1부터 2*n까지의 숫자 중에서 n개를 뽑아야 했기 때문에 조합을 사용하기로 생각했다.

 

조합을 사용해서 각 경우마다 키셋팅에서 퀘스트 숫자가 존재 여부를 확인하며

2차원 배열을 순회할 것이다.

 

int maxNum = 0;

최대 퀘스트 완료 개수를 저장할 변수이다.

 

 

vector<int> arr;
vector<int> comb(n);

for (int i = 1; i <= 2 * n; i++) {
    arr.push_back(i);
}

조합에 필요한 벡터들을 선언해준다.

 

void combination(vector<int> arr, vector<int> comb, int r, int index, int depth) {
    if (r == 0) {
        int cnt = 0;

        for (int i = 0; i < m; i++) {
            bool possible = false;

            for (int j = 0; j < k; j++) {
                std::vector<int>::iterator it = std::find(comb.begin(), comb.end(), quest[i][j]);

                if (it != comb.end()) {
                    possible = true;
                } else {
                    possible = false;
                    break;
                }
            }
            if (possible) {
                cnt++;
            }
        }
        if (cnt > maxNum) {
            maxNum = cnt;
        }
        return;
    } else if (depth == arr.size()) {
        return;
    } else {
        comb[index] = arr[depth];
        combination(arr, comb, r - 1, index + 1, depth + 1);
        combination(arr, comb, r, index, depth + 1);
    }
}

제일 중요한 조합 함수이다.

r, index , depth를 변화시키며 재귀를 통해 모든 경우의 수를 확인하는 방법이다.

 

r이 0이 됐을 때 comb벡터에 조합 중 한 가지 경우가 저장되어있다.

따라서 이때, 2차원 배열의 값(퀘스트)이 comb에 존재하는지 find함수를 통해 확인한다.

만약에 존재한다면 퀘스트를 완료할 수 있는 것이고,

하나라도 키셋팅에 퀘스트를 완료할 수 있는 숫자가 없다면 반복문을 탈출한다.

 

마지막으로 현재 경우에서 완료한 퀘스트의 개수가 maxNum보다 크다면 maxNum을 현재의 완료한 퀘스트의 개수로 바꿔준다.

 

 

combination(arr, comb, n, 0, 0);

메인 함수에서 combination함수를 호출해 조합을 확인하기 시작한다.

 

모든 combination함수가 종료됐다면 maxNum에 문제에서 요구하는 최대로 깰 수 있는 퀘스트의 개수가 저장되어있을 것이다.

cout << maxNum;

출력해주면 끝!

 

 

무엇이 어려웠는가?

조합을 구현하는 것이 제일 어려웠다. 

재귀가 익숙하지 않아서 많이 헷갈렸다. 그래서 결국엔 구글링을 통해 도움을 받았다.

덕분에 기본적인 조합의 틀을 만들 수 있었다.

 

combination 함수에서 문제에서 요구한 대로 퀘스트 완료 개수를 구하는 것은 어렵게 느껴지지 않았다.

그냥 간단한 구현이었다. 다만 find함수의 사용이 익숙하지 않아 사용법을 검색했다.

 

조합을 구현하는 것을 빼면 그다지 어려운 문제가 아니었다고 생각한다. 

 

 

배운 점

 

수학은 정말 어디에서나 쓰이는 구나..

만약 조합이라는 것을 몰랐으면 이 문제는 아예 못 풀었을 것이다.

아직 재귀를 사용하는 것이 매끄럽지 못하다.

더 많은 연습이 필요하다.