[BaekJoon/백준] 1062번 가르침

 

이런 문제 너무 좋다.

 

비트 마스킹 관련 문제인데, 다른 분들의 풀이를 보고 풀었다.

 

그 중에서도, 내가 정말 원하는 방향으로 푸신 분이 있어서 해당 글을 많이 참고했다!!!

 

 

참고로

1 << K 의 의미는, 1을 K번 left shift한 것이다.

 

1 << 0

=> 1이고

 

1 << 1

-> 2이다.

#include <iostream>
#define MAX(a, b) ((a >= b)? a: b)
using namespace std;


int ALPHABET;
int WORDS[50]; // N개(최대50개)의 단어에서, 쓰인 알파벳들을 비트마스킹하여 저장하는 역할.

int N, K;


int TOTAL_MAX = 0;


void dfs(int start, int cnt) {
    
    
    if(cnt == K) {
        
        int T = 0;
        for(int i = 0; i < N; i++) {
            
            if((WORDS[i] & ALPHABET) == WORDS[i])
                T++;
            
        }
        TOTAL_MAX = MAX(T, TOTAL_MAX);
        return;
    }
    
    
    for(int i = start; i < 26; i++) {
        
        if(!(ALPHABET & (1 << i))) {
            
            ALPHABET |= (1 << i);
            
            dfs(i + 1, cnt + 1);
            
            ALPHABET &= ~(1 << i);
            
        }
        
    }
    
    
}

int main() {
    
    // anta, tica는 무조건적으로 들어가므로, 1로 비트마스킹
    // .. 은 너무 길어서 생략한다는 의미로 주석 달았음.
    ALPHABET |= (1 << ('a' - 'a')); // .... .... .... .... .... 0001
    ALPHABET |= (1 << ('n' - 'a')); // .... .... ..10 0000 0000 0001
    ALPHABET |= (1 << ('t' - 'a')); // .... 1000 0010 0000 0000 0001
    ALPHABET |= (1 << ('i' - 'a'));
    ALPHABET |= (1 << ('c' - 'a'));
    
    
    string str;
    
    cin >> N >> K;
    
    for(int i = 0; i < N; i++) {
        
        cin >> str;
        
        int sz = str.length();
        
        for(int j = 0; j < sz; j++)
            WORDS[i] |= (1 << (str[j] - 'a'));
    }
    
    
    if(K < 5)
        cout << 0 << "\n";
    else if(K == 26)
        cout << N << "\n";
    else {
        
        K -= 5; // a, n, t, i, c => 5개는 기본적 뽑았으니 갯수에서 제외해야함.
        
        dfs(0, 0);
        cout << TOTAL_MAX << "\n";
    }
    
}

 

 

 

꼭 참고하세요!!

https://onlytrying.tistory.com/154

 

소요 시간 : 1시간 10분