(C++) - 백준(BOJ) 1062번 : 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

효율적으로 탐색해야하는 문제였습니다.

 

풀이방법

 그냥 있는대로 탐색한다면 조합을 뽑는데 최대 26C13이 나오므로 1천만의 시간복잡도 가집니다. 따라서 뽑은 후 50 * 15를 하면서 최대 단어의 개수를 구하므로 50 * 15 * 1천만 = 7억 5천정도의 시간복잡도로 시간초과에 걸립니다. 따라서 효율적인 탐색방법을 고안해야합니다.

 먼저 모든 단어는  "anta"로 시작되고, "tica"로 끝납니다. 이 말은 다섯개의 문자 'a', 'n', 'c', 'i', 't'를 무조건 배워야 적어도 해당 단어를 알아들을 수 있다는 의미가 됩니다. 따라서 해당 문자 5개를 지운 후 조합을 계산하면 최악은 (26 - 5) C 11이 되므로 40만보다 적은 시간복잡도로 제한에 걸리지 않습니다.

 

 1. 문자를 저장할 때 앞 "anta" 뒤 "tica"를 제외한 나머지 단어들을 words라는 vector<string> 변수에 삽입합니다.

 

 2. 만약 k < 5라면 단어를 알아들을 수 있는 것이 없으므로 0을 출력 후 프로그램을 종료합니다.

 

 3. dfs를 수행합니다.

 수행하면서 한 조합("bdefghjklmopqrsuvwxyz" 중 k-5개)을 뽑았을 때 마다 map에 뽑은 문자들을 저장합니다.  그 후  모든 words들에 대해 한 글자씩 확인하면서 해당 단어를 알아들을 수 있는지를 판단합니다.

words에는 이미 배운 다섯개의 문자가 포함되어 있을 수 있기 때문에 이를 건너뛰고 나머지 문자들에 대해만 map에 있는지 확인해줍니다. 모든 words들에 대해 유효한 개수를 세주었으면 ans변수를 최대값으로 갱신해줍니다.

 

 4. 정답을 출력합니다.

 

* bitmasking으로 이미 가르친 알파벳이 있는지에 대한 비교를 O(1)만 할 수 있기에 보다쉽게 구현할 수 있습니다.

Code

일반 backtracking

#include <bits/stdc++.h>
using namespace std;
int n, k, ans, ck[26];
vector <string> words;
string comb,alphas = "bdefghjklmopqrsuvwxyz";
void dfs(int depth, int idx){
    if(depth == k - 5){
        int cnt = 0;
        map <char,int> m;
        for(auto &a : comb) m[a] = 1;
        for(int i = 0; i < words.size(); i++){
            int flag = 0;
            for(auto &cur : words[i]){
                if(cur == 'a' || cur == 'n' || cur == 'c' || cur == 'i' || cur == 't') continue;
                if(!m[cur]) {flag = 1; break;}
            }
            if(!flag) cnt++;
        }
        ans = max(ans,cnt);
        return;
    }

    for(int i = idx; i < alphas.size(); i++){
        if(ck[i]) continue;
        ck[i] = 1;
        comb.push_back(alphas[i]);
        dfs(depth + 1, i + 1);
        comb.pop_back();
        ck[i] = 0;
    }   
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        map<char,int> tmp;
        string s, t;
        cin >> s;
        string part = s.substr(4, s.size() - 8);
        for(int i = 0; i < part.size(); i++) tmp[part[i]] = 1;
        for(auto el : tmp) t += el.first;
        words.push_back(t); 
    }

    if(k < 5) { //'a', 'n', 't', 'i', 'c'도 못가르친다면 단어를 읽을 수 없다.
        cout << 0; return 0;
    }
    
    dfs(0,0);

    cout << ans << '\n';
}

 

bit masking

#include <bits/stdc++.h>
using namespace std;
int n, k, teached;
int words[51];

int backtracking(int depth, int idx){
    int ret = 0;
    if(depth == k - 5){
        for(int i = 0; i < n; i++){
            if((words[i] & teached) == words[i]) ret++;
        }
        return ret;
    }

    for(int i = idx; i < 26; i++){
        if(teached & (1<<i)) continue;
        teached |= (1 << i);
        ret = max(ret,backtracking(depth + 1, i + 1));
        teached &= ~(1 << i);
    }
    return ret;
}

int main(){
    cin >> n >> k;
    string w;
    for(int i = 0; i < n; i++) {
        cin >> w;
        for(int j = 0; j < w.size(); j++) words[i] |= 1 << (w[j] - 'a');
    }
    if(k < 5) {cout << 0; return 0;}
    teached |= 1 << ('a' - 'a');
    teached |= 1 << ('c' - 'a');
    teached |= 1 << ('i' - 'a');
    teached |= 1 << ('t' - 'a');
    teached |= 1 << ('n' - 'a');

    cout << backtracking(0,0);

}