BJ G4 1062 가르침

BJ G4 1062 가르침

 

 

문제링크

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

1062번: 가르침

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 어떤 알파벳을 배우느냐 배우지 않느냐의 선택 문제. 하지만 이들의 순서는 무관하기 때문에 조합적 문제
   - 총 26개의 알파벳에서 K개를 골라야 한다.
   - 하지만 모든 단어는 anta로 시작하고 tica로 끝나기 때문에 a,n,t,i,c이 다섯 글자는 반드시 알아야 한다.
   - 따라서 전체적으로는 21 글자에서 K-5개를 고르는 경우
   - K가 5보다 작을 때는 의미 없다.

 * 배울 수 있는 알파벳은 총 26글자.
   - 이들의 상태를 관리하기 위해 26 크기의 boolean 배열을 써도 되지만
   - 단순히 int 하나를 이용한 bitmasking을 쓴다면 훨씬 효율적인 탐색 가능
   - & 연산: 포함하는지(이미 배웠는지) 알아보기
   - | 연산: 포함시키기

입력사항

 * 단어의 개수 N: 50보다 작거나 같은 자연수
 * 가르칠 글자 K: 26보다 작거나 같은 자연수 또는 0
 * 단어는 모두 영문 소문자로만 이루어져 있으며 길이는 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않음

출력사항

 * K 개의 글자를 가르칠 때 학생들이 읽을 수 있는 단어 개수의 최대 값

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/4hxTn27uaxA

YouTube

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class BJ_G4_1062_가르침 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int N;// 단어의 개수 N은 50보다 작거나 같은 자연수이고
    static int K;// 배울 알파벳 수 K는 26보다 작거나 같은 자연수 또는 0

    static int status;
    static int Max;
    static int[] wrodBits;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        StringTokenizer tokens = new StringTokenizer(input.readLine(), " ");
        N = Integer.parseInt(tokens.nextToken()); //
        K = Integer.parseInt(tokens.nextToken());
        wrodBits = new int[N];
        for (int i = 0; i < N; i++) {
            wrodBits[i] = wordToBit(input.readLine());
        }

        // System.out.println("비트 변환 확인: "+Arrays.toString(strs));
        // a,n,t,i,c를 못배우면 읽을 수 있는게 전무
        if (K < 5) {
            System.out.println(0);
            return;
        }

        // antic 배우기
        status = wordToBit("antic");
        // System.out.println("상태 확인: "+status);

        String other = "bdefghjklmopqrsuvwxyz"; // antic를 제외한 나머지 알파벳 - 누구를 배울 것인가? 순서 무관 --> 조합 문제

        // 읽을 수 있는 최대 개수
        Max = Integer.MIN_VALUE;

        makeCombination(other, K - 5, 0, status);

        System.out.println(Max == Integer.MIN_VALUE ? 0 : Max);
    }

    static void makeCombination(String src, int r, int si, int status) {
        if (r == 0) {
            // 다 뽑았다면 체크해보기
            // System.out.println(Integer.toBinaryString(status));
            int cnt = 0;
            for (int wordBit : wrodBits) {
                // 단어인 wordBit를 읽으려면 status에 모든 내용이 있어야 가능
                if ((wordBit | status) == status) {
                    cnt++;
                }
            }
            Max = Math.max(cnt, Max);
            return;
        }
        for (int i = si; i < src.length(); i++) {
            char c = src.charAt(i);
            // 이미 읽을 수 있으면 생략
            if (canRead(status, c)) {
                continue;
            }
            makeCombination(src, r - 1, i, learn(status, c));
        }
    }

    static int learn(int status, char c) {
        return status | 1 << (c - 'a');
    }

    static boolean canRead(int status, char c) {
        return (status & 1 << (c - 'a')) > 0;
    }

    static int wordToBit(String src) {
        int status = 0;
        for (int i = 0; i < src.length(); i++) {
            status = learn(status, src.charAt(i));
        }
        return status;
    }

    static boolean check(int status, String src) {
        for (int i = 0; i < src.length(); i++) {
            if (!canRead(status, src.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    private static String src = "3 6\r\n" +
                                "antarctica\r\n" +
                                "antahellotica\r\n" +
                                "antacartica";
}