백준_가르침_1062

문제 링크

조건

• 모든 단어는  anti  로 시작,  tica  로 끝남

 

접근 방법

•  a  ,  c  ,  i  ,  n  ,  t   5개의 문자는 기본으로 배워야 함
  • check[] boolean 배열에 5개의 문자는 true로 표시
  • 나머지 21개 문자를 대상으로 조합 dfs
  • 조합 결과를 기준으로 읽을 수 있는 문자 개수 카운트

 

솔루션

public class Main {

	static int N,K;//단어 개수, 가르칠 글자 개수
	static int[] combi;
	static boolean[] check;
	static String[] words;
	static int max;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		check = new boolean[26];
		check['a' - 'a'] = check['c' - 'a'] = check['i' - 'a'] = check['n' - 'a'] = check['t' - 'a'] = true;
		
		words = new String[N];
		for(int i = 0; i < N; i++) {
			words[i] = br.readLine().trim();
		}
		
		K -= 5;//기본으로 배워야 할 단어 개수 빼줌
		if(K > -1) dfs(0,0);
		
		System.out.println(max);
	}
    
	private static void dfs(int idx, int cnt) {//배울 글자 조합 dfs
		if(cnt == K) {
			checkAns();
			return;
		}
		
		for(int i = idx; i < 26; i++) {
			if(check[i]) continue;//이미 배운 글자
			check[i] = true;
			dfs(i+1, cnt+1);
			check[i] = false;
		}
	}
	
    private static void checkAns() {//읽을 수 있는 문자열 개수 count
		int count = 0;
		for(int i = 0; i < N; i++) {
			String tmp = words[i];
			int len = tmp.length();
			boolean isAble = true;
			for(int j = 4; j < len-4; j++) {
				if(!check[tmp.charAt(j) - 'a']) {
					isAble = false;
					break;
				}
			}
			if(isAble) count++;
		}
		
		max = count > max ? count : max;
	}
	
}

 

리뷰

• 전형적인 조합 문제