[C++] 백준 1497번: 기타콘서트

🔗 문제

https://www.acmicpc.net/problem/1497

 

최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.

 

✏️ 풀이

 

조건

• N ≤ 10, 자연수
• M≤ 50, 연수

 

알고리즘

• 조합
• 비트 마스킹

몇 대의 기타를 조합해야지 모든 곡을 다 칠 수 있을까? 즉, n개 중에 r개를 뽑았을 때 최대 곡수를 전역으로 저장해뒀다가 최소 r를 갱신해주면 된다.

이 때 유의할 것은 최대 M이 50이며, 모든 곡들을 순회하면 속도가 느리다는 것이다. 그래서 바로 비트 마스킹을 떠올릴 수 있었고 int의 범위가 넘어가기 때문에 `long long`을 해주는 것이 포인트다.

어렵지 않지만 굳이 풀이를 쓰는 이유는 반드시 마스킹할 때 `1LL`에서 밀어주기. 간과했다가 틀렸습니다를 봤기 때문에 작성해본다.

 

 

고통받는 cpp 유저가 없길 바라며 ~~ 총총

long long mask = 0b0;
cin >> guitar >> inp;
for(int j=0; j<M; ++j)
{
    if(inp[j] == 'Y')
        mask|= (1LL << (M-1-j)); // LL는 반드시 해줘야한다. (테스트 해봄)
}
guitars[i] = mask;

 

💾  소스

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<long long> guitars;
int N, answer = 1e9;
long long tmp = 0; // 가장 많이 친 곡 수 

void dfs(const int depth, const int cnt, const long long mask)
{
    if (mask == tmp && answer > cnt)
    {
        answer = cnt;
    }
    else if(mask > tmp)
    {
        tmp = mask;
        answer = cnt;
    }

    if(depth == N)
        return;

    dfs(depth+1, cnt+1, (mask | guitars[depth]));
    dfs(depth+1, cnt, mask);
}

int main()
{
    string guitar, inp;
    int M;

    cin >> N >> M;

    guitars.resize(N);
    for(int i=0; i<N; ++i)
    {
        long long mask = 0b0;
        cin >> guitar >> inp;
        for(int j=0; j<M; ++j)
        {
            if(inp[j] == 'Y')
                mask|= (1LL << (M-1-j)); // LL는 있어야 한다..
        }
        guitars[i] = mask;
    }

    dfs(0, 0, 0);

    cout << (answer == 0 ? -1 : answer);

    return 0;
}