1062. 가르침

백준 1062번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1062번: 가르침

풀이

아이디어

모든 남극 단어는 “anta”와 “tica”로 시작하기 때문에 ‘a’, ‘n’, ‘t’, ‘i’, ‘c’ 이 적어도 5개의 알파벳을 모르면 어떤 남극 단어도 읽을 수가 없다.

따라서 K는 적어도 5 이상이어야 하고, 만약 5 미만이라면 0을 출력하도록 했다.

그 이후에는 know_alpha 배열에 아는 알파벳들을 체크해주고, 체크한 알파벳의 개수가 K개가 되면 (a, n, t, i, c를 포함해서 세어줘야 한다는 것에 주의하기) 주어진 단어들을 순회하며 아는 알파벳들로 읽을 수 있는 단어를 체크하는 DFS로 문제를 풀어주었다.

dfs를 이용할 줄만 알면 별로 까다로운 부분 없이 풀 수 있는 문제였던 것 같다. 물론 나는 k-5 부분 빼먹어서 몇번 고생하긴 했지만…;;

코드

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

vector<string> word_list;
bool know_alpha[26];
int n, k, answer;
bool check_alpha[26];

void init_alpha();
void dfs(int idx, int cnt);
int get_can_read();

int main(){
    string word, sub;
    cin >> n >> k;

    if (k < 5){
        cout << 0;
        return (0);
    }
    for(int i = 0; i < n; i++){
        cin >> word;
        // anta 와 tica 가 매번 중복되기 때문에 그 부분을 빼고 저장해줌
        sub = word.substr(4, word.length() - 8);
        word_list.push_back(sub);
    }
    init_alpha();
    dfs(0, 0);
    cout << answer;
    return (0);
}

void init_alpha(){
    memset(know_alpha, false, 26);
    know_alpha['a' - 'a'] = true;
    know_alpha['n' - 'a'] = true;
    know_alpha['t' - 'a'] = true;
    know_alpha['i' - 'a'] = true;
    know_alpha['c' - 'a'] = true;
    k -= 5;
}

void dfs(int idx, int cnt){
    if (cnt == k){
        int cnt_can_read = get_can_read();
        answer = max(answer, cnt_can_read);
        for(int i = 0; i < 26; i++){
            check_alpha[i] = know_alpha[i];
        }
        return;
    }
    for(int i = idx; i < 26; i++){
        if(know_alpha[i] == true)
            continue;
        know_alpha[i] = true;
        dfs(i, cnt + 1);
        know_alpha[i] = false;
    }
}

int get_can_read(){
    int cnt = 0;
    bool can_read;
    string word;
    for(int i = 0; i < word_list.size(); i++){
        word = word_list[i];
        can_read = true;
        for(int j = 0; j < word.length(); j++){
            if(know_alpha[word[j] - 'a'] == false){
                can_read = false;
                break;
            }
        }
        if(can_read == true)
            cnt++;
    }
    return (cnt);
}