문제 바로가기

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

문제 소개 및 재정의

영어 알파벳 26개중 K개를 가르칠수 있다.
이때 읽을수 있는 단어의 개수의 최대값을 구하시오.
단어에는 "anta"와 "tica"가 필수적으로 들어간다.
단어의 개수는 50개 이하의 자연수이다.
K는 0이상 26이하의 정수이다.
단어는 소문자로만 이루어져있고, 길이는 8~15이다.

K개의 알파벳을 어떤 set으로 가르쳐야 최대한 많은 단어를 읽을수 있는지 고민해야한다.
다시 말하면 위의 조건을 만족하는 최적의 조합을 구해야 한다는 말이다.

문제 패턴

문제 상황이 주어지고, 조합에 따라 해결력이 다르다고 할때.
제일 좋은 조합을 찾는 문제이다.

어떻게 풀까? - 완전탐색

포인트

26개에서 K개를 고르는 조합의 경우의 수는 26CK 이다.
이때 조합의 최대값은 K가 13일때이다. (파스칼의 삼각형 참고)
26C13 은 대략적으로 107 = 천만 정도이다.
퍼포먼스상 대략 천만개의 조합은 커버 가능하다.
하나의 조합당 50개의 단어, 최대 15의 길이를 가진 단어를 검사해야하므로.
50*15=750 번의 연산이 필요하다고 예상된다.
그럼 전체 연산은 천만 X 750 = 75억 이 된다.
아, 이건 완탐으로 주어진 시간내에 안될텐데.

그래서 그런지 문제에서는 "anta"와 "tica"라는 조건을 추가한듯 하다.
"anta"와 "tica"는 [a,c,i,n,t] 5개의 알파벳이 사용된다.
따라서 이 5개는 필수적으로 가지고 있어야 단어를 읽을수 있다.
K가 5미만이라면 읽을수 있는 단어는 0개
5이상이라면 그때부터 조합을 만드는 방식으로 문제를 해결할수있다.
그러면 전체 알파벳 풀의 크기는 26-5=21이 되고.
21C11 = 대략 32만이 된다.
32만 X 750 은 75억의 3%정도 되는 수치이다. (32만이 천만의 3%정도)
75억을 33으로 나누면 대략 2억정도 된다. (32만 X 750 = 240,000,000)
이 정도면 완탐으로 퍼포먼스가 나온다.

조합이 구해지면
각 단어마다.
각 철자마다 조합에 포함돼있는지 검사한다.

• 만약에 포함되지 않았다면, 그 단어는 못 읽는거로 처리한다.
• 만약에 포함되어 있다면, 다음 철자로 넘어간다.

단어의 끝까지 포함돼있다면 해당 조합에서 읽을수 있는 단어의 수를 +1해준다.
마지막 단어까지 검사한 후 읽을수 있는 단어의 수를 여태까지 최대값과 크기를 비교해서 갱신한다.

코드

package study.week12;

import java.io.*;
import java.util.*;
public class BOJ_1062_가르침 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int K;
	static char[][] words;
	static char[] comboK; // 재귀에서 leaf로 태워보낼 리스트. 메모리 아끼기 위함. 안 이래도 되겠는데?
	static char[] fixPool = {'a','n','t','i','c'};
	static char[] realPool = {'b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z'};
	
	static int countMax = 0;
	// 메소드
	//// 조합 구하기.
	static void makeCombo(int nowDigit, int targetDigit, char[] leaf, char[] pool, int start) {
		// 바닥 조건
		if(nowDigit>=targetDigit) {
			// 추가작업
//			System.out.println(Arrays.toString(leaf));
			readWords(leaf);
			return;
		}
		
		// 재귀 파트
		for (int i = 0+start; i < pool.length; i++) {
			leaf[nowDigit] = pool[i];
			makeCombo(nowDigit+1, targetDigit, leaf, pool, i+1);
		}
	}
	
	//// 단어 읽기.
	static void readWords(char[] leaf) {
		int count = 0;
		boolean can = true;
		// 단어들에서 단어순회
		for (int i = 0; i < words.length; i++) {
			char[] word = words[i];
			can = true;	// can == true면 단어를 읽을수있다. false면 못 읽는다. 
			// 단어에서 철자순회
			for (int j = 0; j < word.length; j++) {
				char c = word[j];
				if(canRead(c, leaf)==false) {
					can = false;
					break; // 못 읽는 글자 나옴 => 이 단어 패스 
				}
			} // 철자 순회 종료
			if(can) {
				count++; // 여기에 도착했다는 뜻은 can이 false가 되지 않았다는 뜻. 그 단어를 끝까지 읽었다는 뜻.
			}
		} // 단어 순회 종료
		countMax = Math.max(countMax, count);
	}
	
	//// 읽을수 있는 글자인지 확인.
	static boolean canRead(char c, char[] leaf) {
		// 고정풀에서 읽을수 있으면 트루 리턴
		for (int i = 0; i < fixPool.length; i++) {
			if(fixPool[i]==c) {
				return true;
			}
		}
		// 조합풀에서 읽을수 있으면 트루 리턴
		for (int i = 0; i < leaf.length; i++) {
			if(leaf[i]==c) {
				return true;
			}
		}
		// 여기까지 오면 못 읽는거니까 false 리턴
		return false;
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		words = new char[N][];
		for (int i = 0; i < N; i++) {
			words[i] = input.readLine().toCharArray();
		}
		// 세팅
		comboK = new char[K];
		// 작업
		if(K<5) {
			System.out.println(countMax);
		} else {
			K-=5; // 고정풀에서 K개중에서 5개를 이미 사용함.
			makeCombo(0, K, new char[K], realPool, 0);
			System.out.println(countMax);
		}
		// 출력
		
	}// 메인 종료

}

퍼포먼스

[ 13,260 KB | 592 ms ]

마무리

realPool을 리터럴로 넣지 말고, ASCII 코드를 활용해서 생성하는 메서드로 만들었으면 더 깔끔하고, 휴먼에러가 없어질것 같은 코드인것 같다.