[BOJ 1062] 가르침(시간초과, C++, 40% 틀린이유)

이 문제는 브루트포스 탐색을 통해서 문제를 해결하면 된다.

 

 

 

처음에, 문제를 풀었을 때는 시간초과가 발생했다.

 

 

 

문제의 조건을 살펴보면,

 

 

 

"남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다."

 

 

 

라는 표현이 있다. 이 말의 뜻은, a, n, t, i, c은 무조건 가르쳐야 한다는 것을 의미한다.

 

 

 

만약에, a, n, t, i, c의 문자를 브루트포스 탐색에서 선택 및 제외(조합)할 수 있도록 한다면 시간초과가 발생한다.

 

 

 

이제는 40%대의 실패에 대해서 말씀드리려고 한다.

 

 

 

개인적으로 처음에 문제를 좀 더 효율적으로 풀기 위해서,

 

 

 

anta[*]tica, [*]에 해당하는 문자열들의 알파벳들을 모두 확인해서, 이 알파벳들을 배워야하는 문자들이라고 정의하자.

 

 

 

배워야하는 문자들 > K인 조건을 만족하면, 선택 혹은 제외하는 형식으로 문제를 풀도록 했다.

 

 

 

위와 같이, 문제를 푼다면, 배워야하는 문자들 <= K로 애초에 시작하는 경우에 정답을 찾을 수 없다.

 

 

 

그 예로, N = 1, K = 7, antabbtica의 경우를 생각해보면 이해가 될 것이다.

 

 

 

위의 두 가지 사항을 염두해두고 문제를 풀었다면, 손쉽게 코드를 작성할 수 있다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
vector<string> v;
string tmp;
 
int N, K, c;
int answer = 0;
bool arr[26] = {false};
 
void func(int idx, int cnt){
    if(cnt == K){
        int result = 0;
        for(int i = 0; i < v.size(); i++){
            bool flag = true;
            for(int j = 0; j < v[i].length(); j++){
                if(arr[v[i][j] - 'a'] == false)
                {    
                    flag = false;
                    break;
                }
            }
            if(flag)
                result += 1;
        }
        answer = max(answer, result);
        return;
    }
    
    if(idx == 26)
        return;
    
    if(idx != 0 && idx != 13 && idx != 19 && idx != 8 && idx != 2){
        arr[idx] = true;
        func(idx + 1, cnt + 1);
        arr[idx] = false;
    }
    
    func(idx + 1, cnt);
    return;
}
 
int main() {
    cin >> N >> K;
    arr['a' - 'a'] = true;
    arr['n' - 'a'] = true;
    arr['t' - 'a'] = true;
    arr['i' - 'a'] = true;
    arr['c' - 'a'] = true;
    
    for(int i = 1; i <= N; i++){
        cin >> tmp;
        tmp = tmp.substr(4, tmp.length() - 8);
        v.push_back(tmp);
    }
    
    func(0, 5);
    cout << answer << endl;
    return 0;
}