백준 1062 가르침

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

1062번: 가르침

정말 이문제는 이해를 못한 면도 컸지만 글에 담긴 정보가 많이 부족했던 것 같습니다.

이문제에서 가장 중요한 것은 a n t i c 5개의 문자는 무조건 배운 상태고 나머지에 대해서

K가 6이라면 K-5 이미배운 5개의 알파벳을 제외하고 나머지 알파벳에 21개에 대해서 

K개만큼 뽑으면서 입력으로 들어옴 단어를 최대 몇 개 까지 읽을 수 있는지 출력하는 문제입니다.

 

 

이런 식으로 배운 문자 임을 체크했고 조합같이 26개 중 K-5개의 알파벳을 뽑아 입력된 단어를 몇 개 읽을지

확인하면 됩니다.

아래 소스를 보시고 이해해주세요.

 

#include<stdio.h>
#include<vector>
#include<string>
#include<iostream>
using namespace std;
int N, K;
int Alphabet[26];
string input[52];
int Max = 0;
void dfs(int k, int idx) {
    if (k == K - 5) {
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            int cc = 0;
            for (int j = 0; j < input[i].size(); j++) {
                if (Alphabet[input[i][j] - 'a']) cc++;
                else break;
            }
            if (cc == input[i].size())cnt++;
        }
        if (Max < cnt)Max = cnt;
        return;
    }
    for (int i = idx; i < 26; i++) {
        if (Alphabet[i] == 0) {
            Alphabet[i] = 1;
            dfs(k + 1, i + 1);
            Alphabet[i] = 0;
        }
    }
}
int main(void)
{
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        cin >> input[i];
        input[i].erase(input[i].begin(), input[i].begin() + 4);
        for (int j = 0; j < 4; j++) {
            input[i].pop_back();
        }
    }
    Alphabet['a' - 'a'] = Alphabet['n' - 'a'] = Alphabet['c' - 'a'] = Alphabet['i' - 'a'] = Alphabet['t' - 'a'] = 1;
    dfs(0, 0);
    printf("%d", Max);
    return 0;
}