[백준] 가르침 (비트마스킹)

문제 소개

가르침 - 백준 1062번 문제를 정리합니다.
이 문제는 최대 K개의 글자를 가르칠 수 있을 때, 읽을 수 있는 단어의 최대 개수를 구하는 비트마스킹 + 백트래킹 문제입니다.
핵심은 반드시 포함해야 하는 5글자(a, n, t, i, c)를 고려한 조합 탐색과,

비트 연산으로 빠르게 단어 읽기 여부를 판별하는 방식에 있습니다.

문제 링크: 가르침 - 백준 1062번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 모든 단어는 "anta"로 시작하고 "tica"로 끝남 → 항상 필요한 5글자(a, n, t, i, c)는 미리 배운 상태에서 시작
2. 단어의 나머지 글자를 비트마스킹으로 저장
3. K < 5이면 어떤 단어도 읽을 수 없음 → 바로 0 출력
4. K == 26이면 모든 글자를 배운 것과 같음 → 모든 단어 읽을 수 있음
5. 그렇지 않다면, 조합으로 21개의 나머지 글자 중 K-5개를 선택
6. 선택된 알파벳으로 비트 연산을 통해 모든 단어가 읽히는지 확인

---

해결 과정 및 코드

핵심 아이디어

1. 단어마다 a, n, t, i, c를 제외한 중간 부분만 비트마스킹 처리
   → 예: "antahellotica" → "hello" → 각 문자를 비트로 OR 연산
2. 모든 조합(21C(K-5))을 탐색하면서 현재 학습한 문자 집합(비트)이 각 단어의 문자 집합을 포함하는지 검사
3. 포함되면 그 단어는 읽을 수 있음 → 카운팅
4. 최대 읽을 수 있는 단어 개수를 갱신

코드

시간 복잡도 :O(21C(K-5) × N)
이유: 21개의 선택 가능한 문자 중 K-5개 조합, 각 조합에 대해 N개의 단어를 검사

 

import java.util.*;
import java.io.*;

public class Main {
    static int N, K, max;
    static int[] words;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = read(); // 단어 개수
        K = read(); // 배울 수 있는 문자 수
        words = new int[N];

        // 단어 입력 처리
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            int len = word.length();
            for (int j = 4; j < len - 4; j++) { // "anta"와 "tica" 제외
                int charIndex = word.charAt(j) - 'a';
                words[i] |= (1 << charIndex); // 비트마스크에 문자 기록
            }
        }

        if (K < 5) {
            bw.write("0"); // a, n, t, i, c를 못 배우면 아무 단어도 못 읽음
        } else if (K == 26) {
            bw.write(Integer.toString(N)); // 모든 알파벳 배움
        } else {
            int learn = 0;
            learn |= 1 << ('a' - 'a');
            learn |= 1 << ('n' - 'a');
            learn |= 1 << ('t' - 'a');
            learn |= 1 << ('i' - 'a');
            learn |= 1 << ('c' - 'a');

            max = 0;
            learnComb(0, 0, learn); // 나머지 K-5개 조합 탐색
            bw.write(Integer.toString(max));
        }

        bw.flush();
    }

    // 가능한 문자 조합 탐색 (조합 + 백트래킹)
    static void learnComb(int startIdx, int select, int learn) {
        if (select == K - 5) {
            int cnt = 0;
            for (int word : words) {
                if ((word & learn) == word) cnt++; // 단어에 필요한 모든 문자를 배웠는지 확인
            }
            max = Math.max(max, cnt);
            return;
        }

        for (int i = startIdx; i < 26; i++) {
            if ((learn & (1 << i)) != 0) continue; // 이미 배운 문자면 패스
            learnComb(i + 1, select + 1, learn | (1 << i)); // 새 문자 추가
        }
    }

    // 빠른 입력 처리
    static int read() throws Exception {
        int n = System.in.read() & 15, cur;
        while ((cur = System.in.read()) > 32)
            n = (n << 3) + (n << 1) + (cur & 15);
        return n;
    }
}