백준 1497번 [기타콘서트](C++) -yes6686- 티스토리

백준 문제 풀이: 1497 [기타콘서트]

---

문제 링크: https://www.acmicpc.net/problem/1497

문제 설명:

여러 기타와 각 기타가 연주할 수 있는 곡의 정보를 입력받아, 최대한 많은 곡을 연주할 수 있도록 기타를 선택합니다. 목표는:

1. 최대 곡 수를 연주할 수 있는 경우를 찾는다.
2. 같은 곡 수를 연주할 수 있는 경우에는 기타를 최소로 사용하는 경우를 선택한다.

기타와 곡의 상태를 비트마스크로 표현하여 효율적으로 계산합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

string s[11]; // 기타 이름 저장
long long int arr[51]; // 각 기타가 연주 가능한 곡 상태를 비트마스크로 저장

int n, m; // 기타 수, 곡 수
int maxGitCnt = -1; // 최소 기타 개수
int maxPlayCnt = 0; // 최대 연주 가능한 곡 수

// 백트래킹 함수
void go(int d, long long int fs, int gCnt, int pCnt) {
    if (d >= n) {
        if (pCnt == 0) return; // 한 곡도 연주할 수 없는 경우

        if (maxPlayCnt < pCnt) {
            maxPlayCnt = pCnt;
            maxGitCnt = gCnt;
        } else if (maxPlayCnt == pCnt) {
            if (maxGitCnt == -1 || maxGitCnt > gCnt) {
                maxGitCnt = gCnt;
            }
        }
        return;
    }

    // 현재 기타 선택
    long long int newFs = fs | arr[d]; // 곡 추가
    int newPlayCnt = 0;
    for (int i = 0; i < m; i++) {
        if (newFs & (1LL << i)) { // 비트가 켜져 있으면 곡 연주 가능
            newPlayCnt++;
        }
    }
    go(d + 1, newFs, gCnt + 1, newPlayCnt);

    // 현재 기타 선택하지 않음
    go(d + 1, fs, gCnt, pCnt);
}

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

    cin >> n >> m;

    // 기타와 곡 정보 입력
    for (int i = 0; i < n; i++) {
        string a;
        cin >> s[i] >> a;
        for (int j = 0; j < a.size(); j++) {
            if (a[j] == 'Y') {
                arr[i] |= (1LL << j); // 곡을 비트마스크로 저장
            }
        }
    }

    // 백트래킹 시작
    go(0, 0, 0, 0);

    cout << maxGitCnt << '\n'; // 결과 출력

    return 0;
}

예제 입력:

3 4
Gibson YYNN
Fender NYYN
Yamaha NNYN

예제 출력:

2

---

코드 설명

• 핵심 알고리즘: 백트래킹과 비트마스크를 사용하여 기타 선택의 모든 경우를 탐색하고, 최대 곡 수를 연주할 수 있는 조합을 찾습니다.
• 구현 세부사항:
  • arr[i]: 각 기타가 연주할 수 있는 곡 정보를 비트마스크로 저장합니다.
  • 백트래킹 함수 go는 현재 기타를 선택하거나 선택하지 않는 두 가지 경우를 탐색합니다.
  • 곡 수와 기타 수를 갱신하며 최적의 조합을 찾습니다.
• 시간 복잡도: O(2^n ⋅ m), 여기서 n은 기타의 수, m은 곡의 수입니다. n이 작으므로 브루트포스 탐색이 가능.

---

결과

최대 곡 수를 연주할 수 있는 기타 조합을 정확히 계산합니다. 비트마스크와 백트래킹을 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!