[백준/Baekjoon] 1497 기타콘서트 C++ :: Brute force & Bit masking

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

1497번: 기타콘서트

---

1. Logic

입력 자체가 n <= 10, m <= 50 이기 때문에 완전탐색으로 해결 가능하고 기타로 연주할 수 있는 곡이 10개밖에 안되기 때문에 비트마스킹으로 해결할 수 있을것 같다고 생각했다.

 

1. 비트 마스킹을 통해 노래정보를 비트로 변환하여 저장한다.

2. 연주 가능한 노래의 갯수를 구하는 함수인 countBit를 만들어서 현재  비트 마스킹을 통해 몇번 노래들을 연주할 수 있는지 구한다.

3. 최대 연주 가능 노래 갯수와 기타의 갯수를 갱신하여 정답을 출력한다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

long long songToBit[11];

int n, m;
int ans = 0x3f3f3f3f;
int maxCnt = 0;

int countBit(long long bit) {
    int cnt = 0;
    while(bit) {
        cnt += bit & 1;
        bit >>= 1;
    }
    return cnt;
}

void solve(int idx, long long bit, int cnt) {
    int bitToSong = countBit(bit);
    
    if(bitToSong > maxCnt) {
        maxCnt = bitToSong;
        ans = cnt;
    }
    else if(bitToSong == maxCnt) {
        ans = min(ans, cnt);
    }
    
    if(idx == n) return;
    
    solve(idx+1, bit | songToBit[idx], cnt+1);
    
    solve(idx + 1, bit, cnt);
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        string name, detail;
        cin >> name >> detail;
        
        for(int j = 0; j < m; j++) {
            if(detail[j] == 'Y') {
                songToBit[i] |= (1LL << (m-1-j));
            }
        }
    }
    
    solve(0, 0, 0);
    
    if(!maxCnt) cout << -1;
    else cout << ans;
}

 

---

3. Feedback

비트마스킹

1. &연산자

 - bit & 1 : 제일 오른쪽 비트가 1이면 1 0이면 0 반환

2. |(Pipe) 연산자

 - 두개의 비트를 비교하여 or연산

3. a << b

 - a의 비트를 b칸만큼 왼쪽으로 이동. 제일 오른쪽 비트는 0으로 채워짐.

4. a >> b

 - a의 비트를 b칸만큼 오른쪽으로 이동. 제일 오른쪽 비트는 연산 만큼 사라짐

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐