BOJ 1062 가르침

BOJ 백준 1062 C++

가르침

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

 

풀이 방법에 대해 아주 많이 헤맸던 문제이다.

기본적으로 조합을 한다고는 생각했고, 처음에 생각했던 풀이는

 

N개 단어에 대해 '1개를 선택하는 조합'부터 'N개 선택하기까지의 조합'을 만든다. -> 선택의 갯수가 1부터 N까지로 아주 다양한 조합이 나옴.      문제의 예제로 설명하자면 N=3이므로 [ 1 / 2 / 3 / 1,2 / 1,3 / 2,3 / 1,2,3 ] 7개의 경우가 발생하고,      3보다 조금 더 큰 N=10을 생각하면 훨씬 많은 경우가 발생한다. 각 조합에 대해 사용된 알파벳의 갯수를 세고 K개 이하일 때 ans값이 최대인지 확인하여 갱신한다. .. 라고 풀이하려했으나, N=50까지 가능하므로 TLE 가능성 100% 로 당.연.히. 불가능한 풀이임을 알 수 있었다.

 

---

 

 

TLE가 발생하는 풀이밖에 생각나지 않아서 한참을 고민했다.

결론적으로 이 문제는 '주어지는 단어의 수'를 조합하는 것이 아니고 '배울 알파벳 갯수'를 조합하는 것이었다.

 

우선, 전처리를 해야한다.

남극의 모든 단어는 "anta"로 시작하고 "tica"로 끝난다. 고 했다.

1) [ a / c / i / n / t ] 를 반드시 배워야한다는 의미이다.

2) 5개를 반드시 배워야하므로 K가 5 미만으로 주어지면 단어가 무엇이 나오는지 볼 필요없이 출력은 0이다.

3) K<5이면 출력이 0인것에 연관하여, K>26이면 모든 알파벳을 알고 있으므로 이 때의 출력은 N이다.

 

 

주어지는 string의 맨 앞 4문자, 맨 뒤 4문자를 제거하여 vector에 넣어두었다.

그리고 check[]에 5개의 문자를 전처리 한 후, dfs를 이용해 배운 알파벳을 표시하였다. 

조합 시, cnt가 K-5 (전처리 한 문자 제외)가 되면 N개의 문자를 확인하여 완전히 배울 수 있는 단어의 갯수를 센다.

그 갯수 중 최댓값을 출력하면 된다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;
bool check[27];
int ans = 0;
vector <string> word;

int wordCount(){
    int ret = 0;

    for(int i=0; i<N; i++){
        string cur = word[i];
        bool flag = true;

        for(int j=0; j<cur.length(); j++){
            if(check[cur[j]-'a']) continue;

            flag = false;
            break;
        }
        
        if(flag) ret++;
    }
    return ret;
}

void dfs(int cnt, int idx){
    if(cnt==K-5){
        ans = max(wordCount(), ans);
        return;
    }

    for(int i=idx; i<26; i++){
        if(check[i]) continue;

        check[i] = true;
        dfs(cnt+1, i);
        check[i] = false;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;

    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        int len = s.length();

        string temp="";
        for(int j=4; j<len-4; j++){
            temp += s[j];
        }
        word.push_back(temp);
    }

    if(K<5) ans = 0;
    else if(K==26) ans = N;
    else{
        check['a'-'a'] = true;
        check['c'-'a'] = true;
        check['i'-'a'] = true;
        check['n'-'a'] = true;
        check['t'-'a'] = true;

        dfs(0,0);
    }
    
    cout << ans;
    return 0;
}