[BOJ 백준] 1062번 : 가르침 (C++)

[BOJ 백준] 1062번 : 가르침 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

https://www.acmicpc.net/problem/1062

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. a~z까지 사용할 수 있는 글자를 비트로 미리 정하기

2. 사용할 수 있는 글자와 각 단어를 비트 or 비교 연산

3. 연산 후 결과와 사용할 수 있는 글자가 같으면, 사용 가능

4. 3번 과정을 모든 단어랑 비교

5. 비교가 끝나면, 최댓값인지 확인하고, 다음으로 사용할 수 있는 글자로 이동(1번으로 이동)

 

과정

 

먼저, 알파벳 소문자는 a부터 z까지 총 26글자로 구성되어 있습니다.

이를 a부터 z까지 순서대로 배치하고, 사용하면 1, 사용하지 않으면 0으로 설정합니다.

이는 총 2^26의 경우가 나타나지만, int의 최댓값인 2^32보다는 작습니다.

그래서, 사용가능한 알파벳 글자 모음을 하나의 int형 데이터로 관리할 수 있습니다.

 

알파벳을 사용할 수 있는 경우는 총 2^26입니다.

하지만, 문제에서 단어의 접두사는 [anta], 접미사는 [tica]가 추가됩니다.

따라서, 알파벳 소문자 [a], [c], [i], [n], [t]는 반드시 사용해야 하는 알파벳입니다.

 

그러므로, 검사하는 경우는 2^26에서 2^21로 줄어듭니다.

이는 시간 복잡도를 생각하면, 10^6 보다는 크고 10^7 보다는 작습니다.

( 2^10 ≒ 10^3 )

 

그렇다면, 이번에는 사용 가능한 알파벳을 구체적으로 정해보겠습니다.

 

1. 먼저, 값을 left shift 연산을 통해 1번 왼쪽으로 밀어줍니다(x2).

2-1. 해당 알파벳을 사용한다면, +1을 더해줍니다.

2-2. 해당 알파벳을 사용하지 않는다면, 값을 더하지 않습니다.

 

간단한, 예시를 통해 확인하겠습니다.

접두사와 접미사로 구성된 [a], [c], [i], [n], [t] 글자만 사용한다고 가정하겠습니다.

 

left shift를 1번 하고 알파벳 a는 사용하므로 +1을 진행합니다.

// a
// 1

 

left shift를 1번 하고 알파벳 b는 사용하지 않으므로, 아무런 값을 더하지 않습니다.

// ab
// 10

 

left shift를 1번 하고 알파벳 c는 사용하므로 +1을 진행합니다.

// abc
// 101

 

 

이러한 과정을 반복했을 때, [a], [c], [i], [n], [t] 글자만 사용한다는 값은 아래와 같습니다.

// abcdefghijklmnopqrstuvwxyz
// 10100000100001000001000000

 

이는 재귀 함수를 통해서 최대 사용 글자 K개 수만큼의 경우를 표현할 수 있습니다.

 

위와 같은 방식으로 단어별로 구성된 알파벳을 int형 데이터로 표현할 수 있습니다.

그래서, 1번 예시의 단어를 int형 데이터로 반환하면, 아래와 같습니다.

// 3 6              abcdefghijklmnopqrstuvwxyz
// antarctica       10100000100001000101000000 -> 6
// antahellotica    10101001100100100001000000 -> 8
// antacartica      10100000100001000101000000 -> 6

추가로, 해당 단어에 대한 1의 개수를 구하는 것은 해당 단어를 구성하는 알파벳 개수와 같은 의미가 됩니다.

그러므로, K개보다 더 많은 알파벳 종류를 사용한 문장은 바로 제외시킬 수 있습니다.

 

이번에는 사용 가능한 글자와 해당 단어를 구성한 알파벳을 비교하겠습니다.

// 3 6              abcdefghijklmnopqrstuvwxyz
// antarctica       10100000100001000101000000 -> 6

//		    abcdefghijklmnopqrstuvwxyz
//[a][c][i][n][r][t]10100000100001000101000000

만약에, [a][c][i][n][r][t]의 알파벳만 사용한다고 하면, or 연산 진행했을 때, 비교 전과 비교 후의 결과가 같습니다.

즉, 여기서 추가로 사용된 알파벳이 없다는 것을 의미하고, 이는 해당 단어를 사용할 수 있다는 뜻입니다.

 

// 3 6              abcdefghijklmnopqrstuvwxyz
// antarctica       10100000100001000101000000 -> 6

//		    abcdefghijklmnopqrstuvwxyz
//[a][c][i][n][s][t]10100000100001000011000000

만약에, 알파벳 글자 r이 아니라 알파벳 글자 s를 사용한다고 하면, or 연산 시 다른 결과가 출력됩니다.

해당 단어와 사용 가능한 알파벳 목록과 or 연산을 진행하면, 아래와 같습니다.

//              abcdefghijklmnopqrstuvwxyz
// 연산 후      10100000100001000111000000 -> 7

따라서, 사용 가능한 알파벳 목록과의 값이 달라지게 됩니다.

값이 달라진다면, 해당 단어는 사용할 수 없다는 뜻을 가집니다.

 

이러한 과정을 반복하면, 정답에 접근할 수 있습니다.

 

주의점

모든 알파벳 소문자인 a부터 z까지 계산하면, 시간 초과가 발생합니다.

그래서, 접두사와 접미사로 구성된 알파벳 글자를 미리 계산하면, 시간 복잡도를 많이 줄여 시간 초과를 방지할 수 있습니다.

---

03. 정답 코드

// 골드 4 - 1062번 : 가르침
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

// 단어 개수 N, K개
// N -> 1~50, K -> 0~26
// 단어는 영어 소문자, 길이 8~15
// 모든 단어 중복 x

// K개 글자만 가르침 -> 학생들은 K개의 글자로만 이루어진 단어를 읽을 수 있음.
// K개의 글자를 가르칠 때 -> 읽을 수 있는 단어 개수가 최대 구하기

// 남극 언어 -> 접두사 : anta, 접미사 : tica

// 최소 K가 5이상 되어야 단어를 읽는 경우가 나옴.
// a n t i c

// 사용 단어를 비트로 변환 
// 단어는 해당 글자가 있으면, 읽을 수 있음.

// ex)
// 3 6              abcdefghijklmnopqrstuvwxyz
// antarctica       10100000100001000101000000 -> 6
// antahellotica    10101001100100100001000000 -> 8
// antacartica      10100000100001000101000000 -> 6

// 9 8              abcdefghijklmnopqrstuvwxyz
// antabtica        11100000100001000001000000 -> 6
// antaxtica        10100000100001000001000100 -> 6
// antadtica        10110000100001000001000000 -> 6
// antaetica        10101000100001000001000000 -> 6
// antaftica        10100100100001000001000000 -> 6
// antagtica        10100010100001000001000000 -> 6
// antahtica        10100001100001000001000000 -> 6
// antajtica        10100000110001000001000000 -> 6
// antaktica        10100000101001000001000000 -> 6

// 처음에 단어 변환 -> 15글자 * 50문장
// K개 이하인 단어로 고정하고 or 연산해서 검사 -> K개 이하 만족 시, +1
// 근데 계속 or을 누적해야 하는데?

// dp랑 섞어야 하나?
// 백트래킹?

// 글자의 개수, 글자 값 -> 글자 값이 더 많은 것을 best로 판단?
// [현재 단어 위치][앞에 단어를 사용한 개수]

// 단어 50개 사용 여부 -> 2^50
// 글자 26개 사용 여부 -> 2^26 중에서 a,c,i,n,t 5개 사용 -> 2^21
// 글자 사용 가능한 것을 int로 변환한 뒤, or 연산해서 같으면, 통과시키기

vector<int> g_words;

// 문장을 bit로 변환
int changeBit(const string& word)
{
    // 글자 존재 여부 확인
    vector<bool> letters(26, false);
    for(const char& each : word)
    {
        letters[each - 'a'] = true;
    }

    // 글자 존재 여부에 따라 비트 계산
    int result = 0;
    for(const bool& letter : letters)
    {
        result = result << 1;
        if(letter) 
            result++;
    }

    return result;
}   

// 단어 입력
void inputWords(const int N)
{
    g_words = vector<int>(N);

    string input;
    for(int i = 0; i < N; i++)
    {
        cin >> input;
        int word = changeBit(input);
        g_words[i] = word;
        // cout << g_words[i] << "\n";
        // cout << bitset<26>(g_words[i]) << "\n";
    }
}


// 해당 허용 글자를 기준으로 몇 개의 단어가 통과되는지 검사
int search(const string letters)
{
    int result = 0;
    // 허용 글자를 숫자로 변환
    int check = changeBit(letters);

    // 각 단어별로 검사
    for(const int& word : g_words)
    {
        // or 연산해서 같으면, 사용할 수 있는 단어로 통과
        if(check == (check | word))
            result++;
    }

    return result;
}

// 허용 글자 정하기
int makeLetter(const string letters, const int idx, const int cnt, const int& K)
{
    // 허용 글자를 모두 정했으면, 탐색
    if(cnt == K)
        return search(letters);

    // 허용 글자를 아직 정하는 중
    int result = 0;

    for(int i = idx; i < 26; i++)
    {
        char letter = i + 'a';
        // 이미 검사한 글자
        if(letter == 'a' || letter == 'c' || letter == 'i' || letter == 'n' || letter == 't')
            continue;

        string next = letters + letter;
        int temp = makeLetter(next, i + 1, cnt + 1, K);
        result = max(result, temp);
    }
    return result;
}


int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 단어 개수 N, 가르칠 글자 수 K
    int N, K;
    cin >> N >> K;

    // 단어 입력
    inputWords(N);

    // 시뮬레이션
    int result = makeLetter("acint", 0, 5, K);

    cout << result << "\n";
}

 

---

04. 마무리

이 문제가 비트 마스킹으로 분류되어 있지 않았다면, 문제를 해결하는데 시간이 더 걸렸을 것 같습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!