[BOJ 1062] 가르침

문제 출처 : https://www.acmicpc.net/problem/1062

 

풀이 :

 

백트래킹 문제입니다.

"anta"와 "tica"는 무조건 포함 되니

알파벳 'a','n','t','i','c' 는 무조건 배워야 합니다.

따라서 k가 5 미만이면 모든 단어를 읽을 수 없습니다.

이를 이용해 알파벳 'a','n','t','i','c'는 무조건 포함된다고 판단하고 5개를 제외한 알파벳 중 k-5개를 뽑는 문제가 되겠습니다.

 

알파벳의 순서는 상관없으니 오름차순으로 뽑아주어 시간을 단축할 수 있습니다.

 

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
 
int n, k, ret,cnt;
bool use[27],ch[27];
string arr[50];
 
bool trash(char c) {
    if (c == 'a' || c == 'n' || c == 't' || c == 'i' || c == 'c')return true;
    return false;
}
 
void back(int itr, int c) {
    if (c == k) {
        int ret1 = 0;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 4; j < arr[i].size() - 4; j++)if (trash(arr[i][j]) || ch[arr[i][j] - 'a'])cnt++;
            if (cnt == arr[i].size() - 8)ret1++;
        }
        if (ret1 > ret)ret = ret1;
        return;
    }
    for (int i = itr; i < 27; i++) {
        if (!use[i] || trash((char)('a' + i)))continue;
        ch[i] = true;
        back(i + 1, c + 1);
        ch[i] = false;
    }
}
 
int main() {
    scanf("%d %d\n", &n, &k);
    k -= 5;
    for (int i = 0; i < n; i++)cin >> arr[i];
    if (k >= 0) {
        for (int i = 0; i < n; i++)for (int j = 4; j < arr[i].size() - 4; j++) {
            if (trash(arr[i][j]))continue;
            if (!use[arr[i][j] - 'a']) {
                use[arr[i][j] - 'a'] = true;
                cnt++;
            }
        }
        if (cnt < k)ret = n;
        else back(0, 0);
    }
    printf("%d", ret);
}