백준 1062 - 가르침

Java

1062 번 - 가르침

문제

접근 방법

기존에 배운 글자는 [a, c, i, t, n]으로 총 5개다.
따라서, 나머지 알파벳 21개 중 k개 만큼 뽑아서 각 단어마다 뽑은 알파벳이 존재하는지 여부를 확인하고, 있으면 그 단어의 개수를 센다.

단어를 뽑는 것은 DFS의 조합으로 해결한다.
알파벳을 뽑는데, 순서를 고려하지 않으므로 조합을 사용하였다.

가장 큰 경우의 수는 21 C 11이며, 이는 352716으로 충분하다.

코드

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

public class Main {
	static int n, k, result;
	static String[] word;
	static boolean[] alpha;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());

    	word = new String[n];

    	String str;
    	for(int i = 0; i < n; i++) {
    		str = br.readLine();
    		word[i] = str.substring(4, str.length() - 4);
    	}

    	alpha = new boolean[26];

		// 문제에서 주어진 글자 5개는 이미 배운 상태이다.
    	alpha['a' - 'a'] = true;
    	alpha['c' - 'a'] = true;
    	alpha['i' - 'a'] = true;
    	alpha['t' - 'a'] = true;
    	alpha['n' - 'a'] = true;

    	k -= 5;

    	if(k < 0)
    		System.out.println(0);
    	else {
    		DFS(1,0);
    		System.out.println(result);
    	}

    	br.close();
	}

	static void DFS(int start, int lv) {
		if(lv == k) {
			int cnt = 0;
			next : for(int i = 0; i < n; i++) {
				for(int j = 0; j < word[i].length(); j++) {		// 각 단어를 확인한다.
					char curC = word[i].charAt(j);
					if(!alpha[curC - 'a']) {		// 현재 단어에 뽑지 않은 알파벳이 존재 하면
						continue next;
					}
				}
				cnt++;
			}
			result = Math.max(result, cnt);
			return;
		}
		// 조합
		for(int i = start; i < 26; i++) {
			if(!alpha[i]) {
				alpha[i] = true;
				DFS(i + 1, lv + 1);
				alpha[i] = false;
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

충분히 해결 가능한 문제였는데, 조합과 순열을 제대로 구별하지 못해 순열의 경우의 수로 판단하고 시간 초과가 날 것이라 생각하여 풀지 못하였다. 이번 기회에 순열과 조합에 대해서 한번더 정리할 기회를 가질 수 있어 좋은 문제였다.

개선할 점