[백준] 1062 가르침 - JAVA

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

1062번: 가르침

해당 문제는 백트래킹 문제였다. 알파벳 배열을 생성하여, 배울 알파벳의 개수 만큼 조합을 만든 뒤, 알파벳을 읽을 수 있는지 판단하면 된다.

처음에 계속 시간초과가 발생하여 애를 먹었는데, 알파벳을 무조건 처음부터 26번째까지 보는 것이 아니라 현재까지 배운 알파벳을 기준으로 다음 알파벳부터 배우면 된다.

 

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

public class Main {
	static boolean[] alph = new boolean[26];
	static String[] words;
	static int N;
	static int K;
	static int max = -1;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		words = new String[N];
		for(int i=0; i<N; i++) {
			words[i] = br.readLine();
		}
		
		if(K < 5) {
			System.out.println(0);
			return;
		}
		
		if(K == 26) {
			System.out.println(N);
			return;
		}
		
		// a, n, t, i, c -> 꼭 들어가는 알파벳이므로 미리 추가
		alph['a'-'a'] = true;
		alph['n'-'a'] = true;
		alph['t'-'a'] = true;
		alph['i'-'a'] = true;
		alph['c'-'a'] = true;
		
		int cnt = 5;
		solution(cnt, 1);
		System.out.println(max);
	}
	
	public static void solution(int cnt, int start) {
		if(cnt == K) {
			// 단어 맞춰보기
			int answer = 0;
			for(String word : words) {
				boolean status = true;
				for(int i=4; i<word.length()-4; i++) {
					if(!alph[word.charAt(i)-'a']) {
						// 배운 단어가 아니라면
						status = false;
						break;
					}
				}
				if(status) answer++;
			}
			max = Math.max(max, answer);
			return;
		}
		
		for(int i=start; i<26;i++) {
			if(!alph[i]) {
				alph[i] = true;
				solution(cnt+1, i+1);
				alph[i] = false;
			}
		}
	}
}