[백준] 1062 가르침

📌 문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

✔ 접근방법

현재 배울 수 있는 알파벳의 수(k-5)만큼의 조합을 만든다고 생각한다.
즉, 백트래킹을 이용해서 배울 수 있는 알파벳의 수 만큼의 조합을 찾아 모든 경우의 수를 고려해준다고 생각하면 된다.

아래 두가지 사항도 고려하여 문제를 풀이한다.
1. anta와 tica를 만족하기 위해 배울 수 있는 알파벳의 수(k)가 항상 5이상의 숫자여야한다.
2. 현재 모르는 알파벳의 수가 배울 수 있는 알파벳의 수보다 적으면 주어진 모든 N개의 단어를 배울 수 있다.

✔ 코드

import java.util.HashSet;
import java.util.Scanner;

public class Main {
	static HashSet<Integer> hs = new HashSet<>();
	static int max = 0;
	static boolean[] alphabet;
	static String[] words;
	static int[] candi;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		alphabet = new boolean[26];

		int n = sc.nextInt();
		int k = sc.nextInt();
		words = new String[n];

		if (k < 5) {
			System.out.println(0);
			return;
		}

		alphabet['a' - 'a'] = true;
		alphabet['n' - 'a'] = true;
		alphabet['t' - 'a'] = true;
		alphabet['i' - 'a'] = true;
		alphabet['c' - 'a'] = true;

		k -= 5;

		for (int i = 0; i < n; i++) {
			words[i] = sc.next();
			for (int j = 0; j < words[i].length(); j++) {
				if (!alphabet[words[i].charAt(j) - 'a']) {
					hs.add(words[i].charAt(j) - 'a');
				}
			}
		}

		// 배울 수 있는 단어보다 모르는 단어가 적은 경우
		if (hs.size() < k) {
			System.out.println(n);
			return;
		}

		boolean[] visit = new boolean[hs.size()];
		candi = new int[hs.size()];
		int index = 0;

		for (int a : hs) {
			candi[index] = a;
			index++;
		}

		comb(0, visit, hs.size(), k);

		System.out.println(max);
	}

	private static void comb(int start, boolean[] visit, int n, int k) {
		if (k == 0) {
			for (int i = 0; i < visit.length; i++) {
				if (visit[i]) {
					alphabet[candi[i]] = true;
				}
			}

			// 읽을 수 있는 단어의 수 확인
			int check = 0;
			for (int i = 0; i < words.length; i++) {
				for (int j = 0; j < words[i].length(); j++) {
					if (!alphabet[words[i].charAt(j) - 'a']) {
						break;
					}
					if (j == words[i].length() - 1)
						check++;
				}
			}

			max = Math.max(max, check);

			for (int i = 0; i < visit.length; i++) {
				if (visit[i]) {
					alphabet[candi[i]] = false;
				}
			}
			return;
		}

		for (int i = start; i < n; i++) {
			visit[i] = true;
			comb(i + 1, visit, n, k - 1);
			visit[i] = false;
		}
	}
}

🖋 회고

문제 읽고 솔직히.. 이건 또 뭔 문제야.. 싶었다 그래도 이런저런 문제를 풀고나니, 백트래킹으로 이용해서 풀면 될 거란 생각이 들었다. (정말 다행)
코드는 점점 길어지고... 반례를 찾지 못해 지칠 때, 질문하기에 있는 기적같은 반례를 보고 문제를 해결했다.

출처 : https://www.acmicpc.net/problem/1962