[BOJ] 가르침 - Compy's Blog

가르침

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ N ≤ 50 1 ≤ K ≤ 26)	BruteForce

와우.. 문제를 정말 신기하게 풀었습니다…

이게 원래 vector, set 이런거 좀 안쓰고 해보려고 했는데 브포 돌리느라 어쩔 수없이 일단 썼는데

이게 접근 방식에 있어서 정해는 맞는 거 같긴한데.. 그니까 N에 대해서 브포를 돌리는게 아니라 K개의 알파벳에 대해서 브포를 돌려서 시간을 최대한 아낀다.. 이런 전략인데 이게 무슨 빠르게 연산하기 위해서 비트마스킹을 하더라구요?!

근데 저는 그걸 안 쓰고 해버려서.. 이게 맞는 접근인 것 같으면서도 이게 실력이 많이 부족하다는 것을 느꼈습니다.

더 노력하겠습니다…ㅠㅜ

정답 코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

bool visited[26];
int n, k;
string words[51];
vector<char> alph;
vector<set<char>> word_chars;
int countReadable() {
    int count = 0;
    for(int i = 0; i < n; i++) {
        bool canRead = true;
        for(char c : word_chars[i]) {
            if(!visited[c - 'a']) {
                canRead = false;
                break;
            }
        }
        if(canRead) count++;
    }
    return count;
}

int mysearch(int index, int learned) {
    if(learned == k || index >= alph.size()) return countReadable();
    
    int result = 0;
    
    visited[alph[index] - 'a'] = true;
    result = max(result, mysearch(index + 1, learned + 1));
    visited[alph[index] - 'a'] = false;
    
    result = max(result, mysearch(index + 1, learned));
    
    return result;
}

int solution() {
    if(k < 5) return 0;
    k -= 5;
    set<char> poss;
    word_chars.resize(n);
    visited['a' - 'a'] = true;
    visited['n' - 'a'] = true;
    visited['t' - 'a'] = true;
    visited['c' - 'a'] = true;
    visited['i' - 'a'] = true;
    for(int i = 0; i < n; i++) {
        cin >> words[i];
        for(int j = 4; j < words[i].size() - 4; j++){
            char c = words[i][j];
            if(visited[c - 'a']) continue;
            poss.insert(c);
            word_chars[i].insert(c);
        }
    }
    alph = vector<char>(poss.begin(), poss.end());

    
    return mysearch(0, 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;

    cout << solution();

    return 0;
}