백준 1497번 기타콘서트

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

문제를 잘 못 읽어서 한참을 고생한 브루트 포스(Brute Force)문제였습니다.(문제를 빨리 읽지 말고 꼼꼼히 읽읍시다 ㅠㅠ)

알고리즘은 아래와 같습니다.

1. 기타의 조합을 모두 확인해봅니다.(재귀 함수 이용)

2. 최대 곡을 갱신할 때마다 maxBit에 최대곡을 result에 기타의 개수를 초기화해줍니다.

3. 최대 곡과 동일한 곡을 연주할 수 있을 경우 result와 cnt를 비교해서 더 작은 값을 result에 넣어줍니다.

4. 만약 최대 곡이 0이라면 곡을 연주할 수 없기 때문에 -1을 출력해주고 1 이상이라면 result를 출력해줍니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int INF = 987654321;

const int MAX = 10 + 1;

 

int N, M;

int maxBit, result;

long long cache[MAX];

 

//비트 내 1 세는 함수

int countBit(long long bit)

{

        int result = 0;

        while (bit)

        {

                 result += bit & 1;

                 bit >>= 1;

        }

        return result;

}

 

void minGuitar(int idx, int cnt, long long bit)

{

        int Y = countBit(bit);

        //핵심은 최대한 많은 곡을 연주하는 것

        //최대 곡을 갱신할 경우

        if (maxBit < Y)

        {

                 maxBit = Y;

                 result = cnt;

        }

        //동일한 곡의 개수일 경우 result 업데이트

        else if (maxBit == Y)

                 result = min(result, cnt);

        //기저 사례 : 마지막 기타까지 확인했음

        if (idx == N)

                 return;

        //해당 기타 선택

        minGuitar(idx + 1, cnt + 1, bit | cache[idx]);

        //해당 기타 선택 X

        minGuitar(idx + 1, cnt, bit);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

        {

                 string name, playList;

                 cin >> name >> playList;

 

                 //비트 계산

                 for (int j = 0; j < M; j++)

                         if (playList[j] == 'Y')

                                 cache[i] |= (1LL << (M - 1 - j));

        }

 

        minGuitar(0, 0, 0);

 

        //곡을 하나도 연주 못할 경우

        if (!maxBit)

                 cout << -1 << "\n";

        else

                 cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~