백준 - 가르침(1062) 정답

문제

1. 문자열(N개)이 주어짐 => 모든 문자에는 공통적으로 알아야 하는 단어들이 존재

2 . 학생들이 알 수 있는 문자의 개수는 총 K개

3. K개의 단어로 읽을 수 있는 문자열의 개수를 출력하는 문제

 

-예시-

K = 6, 총 6개의 단어를 알아야 하기 때문에, a c i n t를 제외한 1개의 단어를 더 알 수 있음

이 때, 그 단어가 r이라면, 1번(antarctica)와 3번(antacartica)를 읽을 수 있어 출력은 2임

 

문제 해결 과정

DFS & back-tracking을 활용

1. 우선적으로 단어 배열을 만듬

2. 단어 배열 중 아직 모르는게 있다면 그 단어를 체크하고 DFS를 통해 다음 단어를 찾으러 들어감

3. 다음 DFS를 위해 back-tracking을 통해 다시 체크 해제

4. DFS를 돌다가, 만일 단어의 개수가 K개라면, 읽을 수 있는 단어를 카운트!

5. 카운트 함수는 flag를 활용함

 

- 코드 -

#include <stdio.h>

#include <string.h>

int N, K, ans;

char words[52][17];

int words_bits[26];

int count_words() {

    int words_num = 0;

    for(int i=0;i<N;i++) {

        int idx = 4;

        int know_flag = 1;

        for(;;) {

            if(words[i][idx] == 0) break;

            if(!words_bits[words[i][idx] - 'a']) {

                know_flag = 0;

                break;

            }

            idx++;

        }

        if(know_flag) words_num++;

    }

    return words_num;

}

void DFS(int n, int idx) {

    if(n >= K) {

        int cnt = count_words();

        ans = (ans > cnt) ? ans : cnt;

        return;

    }

    for(int i=idx;i<26;i++) {

        if(!words_bits[i]) {

            // back tracking

            words_bits[i] = 1;

            DFS(n+1, i);

            words_bits[i] = 0;

        }

    }

}

int main() {

    scanf("%d %d", &N, &K);

    for(int i=0;i<N;i++) scanf("%s", &words[i]);

    // already_know

    words_bits['a'-'a'] = 1;

    words_bits['c'-'a'] = 1;

    words_bits['i'-'a'] = 1;

    words_bits['n'-'a'] = 1;

    words_bits['t'-'a'] = 1;

    if(K <5) {

        printf("%d", 0);

        return 0;

    }

    else {

        K -= 5;

        DFS(0,0);

        printf("%d", ans);

        return 0;

    }

}

 

느낀점

- 문제를 이해하는게 많이 어려웠음... 독해력을 길러야 함...

- while문 대신 for(;;)사용해도 된다