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

백준

 

---

🤔문제 이해

각 퀘스트당 필요한 스킬을 다 사용가능할 때 그 퀘스트를 깰 수 있다. 2n개의 스킬 중 n개만 골랐을 때 최대로 많이 깰 수 있는 퀘스트의 개수를 출력하면 된다.

조건
키의 개수 : n
퀘스트의 개수 : m (1 ~ 100)
퀘스트 당 스킬 수 : k (1 ~ n)
스킬의 번호 ( 1~2n)

---

🔥풀이🔥

2n개의 스킬 중 배치할 스킬 n개를 골랐을 때 깰 수 있는 퀘스트의 개수 중 가장 큰 값을 출력하게 했다.

 

변수

- quest[i] : i번째 퀘스트에서 필요한 스킬의 번호를 비트로 표현

 

재귀함수 void Solve(int i, int d, int cnt) 

- 현재 상태 : 현재까지 정한 스킬을 비트로 나타내는 i, 몇번째 스킬까지 처리해줬는지를 나타내는 d, 정한 스킬의 개수 cnt

- 다음 상태 : d번 스킬을 사용 or d번 스킬을 사용하지 않음

- 진입 상태 : 아무것도 정하지 않은 상태이고 1번 스킬부터 골라야 하므로 Solve(0, 1, 0)

- 종료 상태 : cnt가 n일 때, 즉 n개의 스킬을 골랐을 때 return

- d번 스킬을 사용하게 된다면 i에 해당 스킬 번호의 비트를 켜줌(1로 만들어준다)

 

함수 void CountQuest(int x) 

- 각 퀘스트에서 필요한 스킬의 정보와 정한 n개의 스킬을 AND 연산한 값이 필요한 스킬의 정보와 일치하다면 깰 수 있는 퀘스트의 수를 +1

- 모든 퀘스트와 비교 후 출력할 변수 ans와 비교해 더 큰 값을 ans에 저장

 

✍️ 후기

문제의 입력이 어떻게 들어오는지 제대로 확인하지 않아서 3번이나 틀렸다.

---

#include <iostream>
#include <vector>

using namespace std;

int n, m, k, a;
int quest[102];
int ans;

void CountQuest(int x) {
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if ((quest[i] & x) == quest[i]) {
            cnt++;
        }
    }
    ans = max(ans, cnt);
}


void Solve(int i, int d, int cnt) {
    if (cnt == n) {
        CountQuest(i);
        return;
    } else if (d == 2 * n + 1) return;
    else {
        Solve(i, d + 1, cnt);
        i = i | (1 << d);
        Solve(i, d + 1, cnt + 1);
    }
}


int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            cin >> a;
            quest[i] = quest[i] | (1 << a);
        }
    }
    Solve(0, 1, 0);

    cout << ans;
}