Baekjoon 1062번 가르침

문제

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

걸린 시간

01 : 24 : 47 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, k;
int learn = 0, ans = 0;
string w;
vector<int> word;

void solve(int cnt, int idx, int cur){
    // 기저 사례
    if(cnt == 0){
        int read = 0;
        for(int i = 0; i < n; i++)
            if(word[i] == (word[i]&cur))
                read++;
        ans = max(ans, read);
        return;
    }
    // 재귀 호출
    for(int i = idx+1; i < 26; i++)
        if(!((1<<i)&cur))
            solve(cnt-1, i, cur|(1<<i));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    word.resize(n, 0);
    for(int i = 0; i < n; i++){
        cin >> w;
        w.erase(0, 4);
        w.erase(w.size()-4, w.size());
        for(int j = 0; j < w.size(); j++)
            word[i] |= (1<<((int)w[j]-0x61));
    }
    learn |= (1<<(int)'a'-0x61);
    learn |= (1<<(int)'n'-0x61);
    learn |= (1<<(int)'t'-0x61);
    learn |= (1<<(int)'i'-0x61);
    learn |= (1<<(int)'c'-0x61);
    if(k < 5){
        cout << 0;
    }
    else{
        solve(k-5, -1, learn);
        cout << ans;
    }
    return 0;
}

주어진 단어를 순서대로 호출하며 동시에 학습을 진행하려고 하다보니, 호출하는 순서까지 고려해야하므로 경우의 수가 너무 많았다.

선형 자료구조에 저장된 값들을 알맞은 순서대로 참조해나가는 일반적인 틀에 갇혀 올바른 방법을 생각해내지 못했던 것 같다.

26개의 알파벳 중 k개가 학습되었을 때 읽을 수 있는 알파벳의 개수를 센다면, "anta", "tica" 의 구성 알파벳 5개를 제외한 21개의 알파벳에서 k-5개를 고르는 경우의 수(조합)와 같으므로 완전탐색으로도 제한시간안에 통과할 수 있다. 이때 단어를 비트마스크 기법을 적용하여 정수 형태로 저장한다면 효율을 훨씬 높일 수 있다.