[백준] 1062: 가르침

0. 문제 주소

 

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

1062번: 가르침

 

 

1. 풀이

 

백트래킹이라고 하긴 했지만 가지치기는 안 해서 사실상 완전 탐색 문제

 

 

처음에 시간 초과가 났는데,

 

1. 모든 단어에 포함되어 있는 'a', 'n', 't', 'i', 'c'의 5글자를 빼주지 않아서

2. 조합 경우의 수를 재귀적으로 구할 때 vector를 인자로 전달해줘서

 

등의 이유가 있을 것 같다.

 

시간을 더 줄이려면 비트마스킹도 유용할 듯 하다.

 

어쨌든 choice 배열로 어느 알파벳을 배울 것인가에 대해 모든 경우의 수를 구하고, 그 때의 읽을 수 있는 단어 수를

체크해주면 된다.

 

 

 

2. 풀이 코드

 

* 유의할 점

1. a, n, t, i, c 빼놓기로 시간 줄이기

2. K = 5일 때, antatica 케이스 처리

#include <bits/stdc++.h>
#define MAX 55

using namespace std;

bool alpha[MAX][26];
bool choice[26];
int N, K;
int ans;

void solve(int pos, int cnt){
    if (cnt == K - 5){
        int ret = 0;
        for (int i=0;i<N;i++){
            bool succ = true;
            for (int c=0;c<26;c++){
                if (c == 'a' - 'a' || c == 'n' - 'a' || c == 't' - 'a' || c == 'i' - 'a' || c == 'c' - 'a'){
                    continue;
                }
                if (!alpha[i][c]) continue;

                if (!choice[c]) {
                    succ = false;
                    break;
                }
            }
            if (succ) ret++;
        }

        ans = max(ans, ret);
        return;
    }

    for (int j=pos+1;j<26;j++){
        if (j == 'a' - 'a' || j == 'n' - 'a' || j == 't' - 'a' || j == 'i' - 'a' || j == 'c' - 'a'){
            continue;
        }
        choice[j] = true;
        solve(j, cnt+1);
        choice[j] = false;
    }

    return;

}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;

    if (K < 5) {
        cout << "0\n";
        return 0;
    }
    for (int x=0;x<N;x++){
        string temp;
        cin >> temp;
        int word_size = temp.size();
        for (int i=0;i<word_size;i++){
            if (temp[i] == 'a' || temp[i] == 'n' || temp[i] == 't' || temp[i] == 'i' || temp[i] == 'c'){
                continue;
            }
            alpha[x][temp[i]-'a'] = true;
        }
    }

    if (K == 5){
        solve(0, 0);
    }
    else{
        for (int i=0;i<26;i++){
            if (i == 'a' - 'a' || i == 'n' - 'a' || i == 't' - 'a' || i == 'i' - 'a' || i == 'c' - 'a'){
                continue;
            }
            choice[i] = true;
            solve(i, 1);
            choice[i] = false;
        }
    }

    cout << ans;

    return 0;

}