백준, BOJ, 1062번, 가르침 : C++ [CPP]

시간초과가 왜 난지 몰랐지만..

그냥 나중에 생각해보니 날만했었다.

 

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

 

---

#맞은 풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

bool alpha[26];
int N, K;
vector <string> vec;
int ans = 0;

//idx를 추가시켜서 시간을 단축 시켰다.
//여기서 idx는 for문이 시작하는 번호를 말한다.
void func(int cnt, int idx) {

    //K-5개만큼 골랐다면
    if (cnt == K-5) {
        int cnt = 0;
        //각 단어를 읽을 수 있는지 조사
        for (string str : vec){
            bool read = true;

            //만약 모르는 글자가 나오면 read = false로 만들고 break
            for (char c : str) {
                int x = c - 'a';
                if (alpha[x])continue;
                else { read = false; break; }
            }
            //read가 true상태라면 읽을 수 있음 단어 + 1
            if (read) cnt++;
        }
        ans = max(ans, cnt); //최댓값 갱신

        return;
    }

    //백트래킹(남아있는 알파벳)
    //i를 idx로 초기화 시키지 않고 0으로 했다면 항상 for문은 26번 조사를 했을 것이고
    //해당 for문은 21C(K-5)번이 26번 실행되지 않았나싶다. 거기다 단어조사까지
    // 50 * 15를 하면 시간이 초과될만도 한 것 같다.
    for (int i = idx; i < 26; i++) {
        if (alpha[i] == true)continue; 
        alpha[i] = true;
        func(cnt + 1, i); //idx를 i라고 설정해도 되는 이유 -> 어차피 앞에 것 중복되는 것은 고르지 않아도 된다.
        // 즉 c롤 뻗어나간 트리가 e를 고르나 e로 뻗어나간 트리가 c를 고르나 같은 것이라 새면 손해다.
        alpha[i] = false;
    }
}

int main() {

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

    cin >> N >> K;
    if (K < 5) {
        cout << '0';
        return 0;
    }
    //최소 5개 알파벳 a,n,t,i,c는 알고 있어야 읽을 수 있음(접두어, 접미어)
    //즉, K-5개의 개수만큼 조합을 뽑아서 현재 단어를 읽을 수 있는지 알아냄.
    int n;
    n = 'a' - 'a';
    alpha[n] = true;
    n = 'n' - 'a';
    alpha[n] = true;
    n = 't' - 'a';
    alpha[n] = true;
    n = 'i' - 'a';
    alpha[n] = true;
    n = 'c' - 'a';
    alpha[n] = true;


    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        //접두어 접미어 떼어버림 (어차피 체크함)
        string part = s.substr(4, s.size() - 8); //4번째 부터 0-3 없애고 s.size -8의 크기만큼 substring을 만듬
        vec.emplace_back(part);
    }

    func(0,0);

    cout << ans;





    return 0;
}

 

그냥 코멘트를 보면 된다.

어렵지는 않지만

예외처리가 무척이나 많고 시간복잡도도 신경써야했다.