1062번

1062번 - 가르침

처음에는 각 단어마다 필요한 단어를 구하고, 몇개고 이렇게 구하려다가.. 너무 답이 안보여서

아예 미리 단어를 모두 뽑고, 거기에 맞춰서 읽을 수 있는지 없는지를 판단하는 문제로 풀었다.

근데 처음에 시간초과가 계속 발생해서, 시간초과를 줄이려고 노력했다.

그래서 디버깅을 하다 보니, for문을 통해서 할 때의 그 같은 숫자의 반복이 생겼다.

마치 14889번 문제를 풀 때, 하나의 팀으로만 하려니까 중복되는 값이 계속 반복되던 것처럼

그래서 q를 추가해서, 중복되지 않도록 했더니, AC를 받을 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string>
using namespace std;
bool check[26];
int n, k, ans = 0;
void selectWord(int d,int q,vector<string> &str)
{
    if (d == k)
    {
        int t = 0;
        for (int i = 0; i < n; i++)
        {
            bool chk = true;
            for (int j = 4; j < str[i].size()-4; j++)
            {
                if (!check[str[i][j] - 'a'])
                {
                    chk = false;
                    break;
                }
            }
 
            if (chk)
            {
                t++;
            }
        }
 
        ans = ans < t ? t : ans;
 
        return;
    }
 
    for (int i = q+1; i < 26; i++)
    {
        if (!check[i])
        {
            check[i] = true;
            selectWord(d + 1,i,str);
            check[i] = false;
        }
    }
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
 
    scanf("%d %d", &n, &k);
    vector<string> str(n);
    for (int i = 0; i < n; i++)
    {
        cin >> str[i];
    }
 
    if (k < 5)
    {
        printf("%d\n", ans);
        return 0;
    }
    else
    {
        check['a' - 'a'] = true;
        check['c' - 'a'] = true;
        check['i' - 'a'] = true;
        check['t' - 'a'] = true;
        check['n' - 'a'] = true;
        k -= 5;
 
        selectWord(0,0,str);
    }
    
    printf("%d\n", ans);
 
 
 
    return 0;
}