[c++] BOJ 1062 :: 가르침

문제

가르침 문제 바로가기

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

 

풀이

• brute force로 찾기 (N이 작음)
• 조건들을 이용하여 최대한 시간복잡도 줄이기

 

코드

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

using namespace std;

vector<string> words;
bool visited[26]; // bit 쓸 데가 이거밖에..
int N, K;
int result = 0;

void getMaxWord(int c ,int count) {
    if (count == K) {
        int tmpResult = 0;
        for (int i = 0; i < words.size(); i++) {
            bool flag = true;
            for (int j = 0; j < words[i].length(); j++) { // 사용 시 여기를 줄일 수 있지만, length는 최대 15
                if (!visited[words[i][j] - 'a']) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                tmpResult++;
        }
        result = max(tmpResult, result);
        return;
    }

    for (int i = c; i < 26; i++) {
        if (!visited[i]) {
            visited[i] = true;
            getMaxWord(i, count + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> N >> K;
    // anta, tica => a n t i c (5)
    // a(0) c(2) i(8) n(13) t(19) 

    for (int i = 0; i < N; i++) {
        string str; cin >> str;
        string midWord;
        midWord.assign(str.begin() + 4, str.end() - 4);
        words.push_back(midWord);
    }

    if (K < 5) {
        cout << 0;
        return 0;
    }
    if (K >= 26) {
        cout << N;
        return 0;
    }

    K -= 5;

    visited[0] = true;
    visited[2] = true;
    visited[8] = true;
    visited[13] = true;
    visited[19] = true;

    getMaxWord(0, 0);
    cout << result << '\n';
}

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2024	140	1165

근데 나 bitmap 안썼는디..

bitmap 사용하면 visited 배열을 bit로 만들어서 연산하는 방법을 사용하여 글자 하나하나 비교하지 않고 비트 연산으로 알파벳 포함 여부를 판단할 수 있을 것 같다.