백준 1062 / C++

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

1062번: 가르침

 

 

[ 풀이 ] 

 

anta와 tica는 디폴트로 가르쳐야 한다. 이 5개를 제외한 글자를 가르치자. 

알파벳이 26개이니 그냥 브루트포스로 21C(k-5)개를 골라주면 된다. 

k-5개를 골라 가르친 후에 N개의 문자열을 읽을 수 있는지 확인해주면 된다.

 

sol 1) 그냥 모든 문자열을 순회하며 읽을 수 있는지 판별한다. 

총 시간복잡도는 O(21Ck-5 * N*15)이고 이 값의 최대는 대충 21C10*50*15 = 2.6억이다. 

백트래킹으로 순회중 적당히 끊는다고 하면 가능한 시간으로 보인다. 

 

sol 2) 문자열 판별을 O(1)에 하는 획기적인 방법이 있다.

비트마스킹을 이용하여  고른 알파벳 상태를 표시 후, N개의 단어를 알파벳 순으로 비트값으로 표현한다. 

그 후에 비교할 땐 (단어)&(고른 알파벳 상태) 이 값이 (단어)가 나와야 고른 알파벳 상태로 그 문자를 읽을 수 있다는

의미가 된다. 멋진 아이디어를 배울 수 있는 문제였다. 

 

 

[ 코드 1 ]  >> 172ms

 

#include <bits/stdc++.h>
using namespace std;
int n, k;
int vis[30];
string str[55];
int ans = 0;

void solve(int idx, int cnt) {
    // 디폴트 알파벳도 못배우면 전부 못읽음 
    if (k < 5) {
        ans = 0;
    }
    // k-5개를 골랐을 때 
    if (cnt == k - 5) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int ok = 1;
            // 순회하며 비교 
            for (int j = 0; j < (int)str[i].size(); j++) {
                int num = str[i][j] - 'a';
                if (!vis[num]) {
                    ok = 0; break;
                }
            }
            if (ok) ret++;
        }
        ans = max(ans, ret);
    }
    // 조합 구현 
    for (int i = idx; i < 26; i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        solve(i, cnt + 1);
        vis[i] = 0;
    }
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> str[i];
    // 디폴트 알파벳 
    vis['a' - 'a'] = 1;
    vis['t' - 'a'] = 1;
    vis['i' - 'a'] = 1;
    vis['n' - 'a'] = 1;
    vis['c' - 'a'] = 1;
    solve(0, 0);
    cout << ans << '\n';
}

 

 

 

 

[ 코드 2 ] >> 28ms

 

#include <bits/stdc++.h>
using namespace std;
int n, k;
int word[55];
int ans = 0;

void solve(int chk, int idx, int cnt) {
    if (k < 5) {
        ans = 0;
    }
    if (cnt == k - 5) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            // 문자열 판단을 O(1)로 줄임
            if ((word[i] & chk) == word[i]) ret++;
        }
        ans = max(ans, ret);
    }
    for (int i = idx; i < 26; i++) {
        if (chk & (1 << i)) continue;
        solve(chk | (1 << i), i, cnt + 1);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        int num = 0;
        // 미리 문자열을 비트마스킹 해놓기 
        for (int j = 0; j < s.size(); j++) {
            num |= 1 << (s[j] - 'a');
        }
        word[i] = num;
    }

    // 디폴트 알파벳 
    int chk = 0;
    chk |= 1 << ('a' - 'a');
    chk |= 1 << ('n' - 'a');
    chk |= 1 << ('t' - 'a');
    chk |= 1 << ('i' - 'a');
    chk |= 1 << ('c' - 'a');
    solve(chk, 0, 0);
    cout << ans << '\n';
}