글 읽기 - 고수님들 도와주세요

hesue615 4년 전 0

비트마스크를 활용하여 문제를 풀었습니다.

도저히 문제를 찾지 못해 이렇게 글 남깁니다.

고수님들의 도움이 필요합니다.

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

using namespace std;

const int MAX = 51;
const int SIZE = 26;
const int BASE = 4;

int n, k;
int THRESHOLD;
int answer;
vector<int> words[MAX];
vector<int> promising;

void dfs (int idx, int select, int mask) {
    if (idx > THRESHOLD) {
        return;
    }

    if (select == k) {
        int cnt = 0;
        
        for (int i = 0; i < n; ++ i) {
            bool flag = true;
            
            for (int j = 0; j < words[i].size(); ++ j) {
                if (!(mask & (1 << words[i][j]))) {
                    flag = false;
                    break;
                }
            }

            if (flag) cnt ++;
        }

        if (answer < cnt) {
            answer = cnt;
        }
        return;
    }
    
    dfs(idx + 1, select + 1, mask | (1 << promising[idx]));
    dfs(idx + 1, select, mask);
}

int main (int argc, const char *argv[]) {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int mask = 0;
    bool check[SIZE] = {false,};

    string pre = "anta";
    string post = "tica";

    for (int i = 0; i < BASE; ++ i) {
        if (!check[pre[i] - 'a']) {
            check[pre[i] - 'a'] = true;
            mask |= (1 << (pre[i] - 'a'));
        }
    }

    for (int i = 0; i < BASE; ++ i) {
        if (!check[post[i] - 'a']) {
            check[post[i] - 'a'] = true;
            mask |= (1 << (post[i] - 'a'));
        }
    }

    cin >> n >> k;

    k -= 5;

    string word;
    for (int i = 0; i < n; ++ i) {
        cin >> word;

        for (int j = BASE; j < word.size() - BASE; ++ j) {
            words[i].push_back(word[j] - 'a');
            if (!check[word[j] - 'a']) {
                check[word[j] - 'a'] = true;
                promising.push_back(word[j] - 'a');
            }
        }
    }

    THRESHOLD = promising.size();

    if (k < 0) {
        cout << "0\n";
    }
    else if (k == 26) {
        cout << n << '\n';
    }
    else {
        dfs(0, 0, mask);
        cout << answer << '\n';
    }

    return 0;
}

kimcoding 4년 전 1

THRESHOLD는 promising.size()를 저장했는데 18번째 줄을 보면 idx > THRESHOLD이라 idx == THRESHOLD일때 밑에 promising[idx]를 처리할때 배열 인덱스를 벗어나게 됩니다.

hesue615 4년 전 1

고수님께서 알려주신대로 인덱스 범위 밖으로 벗어나지 않도록 수정하였습니다.

혹시 다른 로직적인 문제는 없나요?

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

using namespace std;

const int MAX = 51;
const int SIZE = 26;
const int BASE = 4;

int n, k;
int THRESHOLD;
int answer;
vector<int> words[MAX];
vector<int> promising;

void dfs (int idx, int select, int mask) {
    if (idx >= THRESHOLD) {
        return;
    }

    if (select == k) {
        int cnt = 0;
        
        for (int i = 0; i < n; ++ i) {
            bool flag = true;
            
            for (int j = 0; j < words[i].size(); ++ j) {
                if (!(mask & (1 << words[i][j]))) {
                    flag = false;
                    break;
                }
            }

            if (flag) cnt ++;
        }

        if (answer < cnt) {
            answer = cnt;
        }
        return;
    }
    
    dfs(idx + 1, select + 1, mask | (1 << promising[idx]));
    dfs(idx + 1, select, mask);
}

int main (int argc, const char *argv[]) {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int mask = 0;
    bool check[SIZE] = {false,};

    string pre = "anta";
    string post = "tica";

    for (int i = 0; i < BASE; ++ i) {
        if (!check[pre[i] - 'a']) {
            check[pre[i] - 'a'] = true;
            mask |= (1 << (pre[i] - 'a'));
        }
    }

    for (int i = 0; i < BASE; ++ i) {
        if (!check[post[i] - 'a']) {
            check[post[i] - 'a'] = true;
            mask |= (1 << (post[i] - 'a'));
        }
    }

    cin >> n >> k;

    k -= 5;

    string word;
    for (int i = 0; i < n; ++ i) {
        cin >> word;

        for (int j = BASE; j < word.size() - BASE; ++ j) {
            words[i].push_back(word[j] - 'a');
            if (!check[word[j] - 'a']) {
                check[word[j] - 'a'] = true;
                promising.push_back(word[j] - 'a');
            }
        }
    }

    if (promising.empty()) {
        THRESHOLD = 1;
    }
    else {
        THRESHOLD = promising.size();
    }

    if (k < 0) {
        cout << "0\n";
    }
    else if (k == 26) {
        cout << n << '\n';
    }
    else {
        dfs(0, 0, mask);
        cout << answer << '\n';
    }

    return 0;
}

kimcoding 4년 전 1

promising의 단어들을 모두 배울 경우를 봐주지 못하고 있습니다.

18~20줄과 22~42줄의 순서를 바꿔주시면 될 것 같습니다.

밑에는 반례입니다.

[input]
3 10
antarctica
antahellotica
antacartica

[output]
0

[answer]
3

kimcoding 4년 전 1

THRESHHOLD는 anta tica를 제외한 문자를 모은 promising의 사이즈이므로

단어에 나온 문자들을 모두 확인할 수 있고

idx >= SIZE를 하게 되면 promising 범위를 벗어나게 됩니다.

kimcoding 4년 전 2

두 번째 코드에서 반례를 찾아 첫 번째 코드를 다시 수정해서 제출하여 AC를 받았습니다.

k가 promising보다 크게 되면 select가 k와 같을 수가 없어 가능한 단어를 셀 수 없습니다.

select가 k보다 크면 조건에 맞지 않으므로 바로 함수를 리턴하시면 되고

단어를 세는 조건을 promising의 문자들을 확인할지 안할지 다 정하면 idx == THRESHHOLD이므로

그 때 가능한 단어의 개수를 구하면 됩니다.

밑에는 두번째 코드 반례입니다.

[input]
2 15
antabtica
antatica

[output]
0

[answer]
2

hesue615 4년 전 0

다소 시간이 걸렸지만 고수님 덕분에 맞출 수 있었습니다.

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들 도와주세요

hesue615 4년 전 0

kimcoding 4년 전 1

hesue615 4년 전 1

kimcoding 4년 전 1

kimcoding 4년 전 1

kimcoding 4년 전 2

hesue615 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말