[백준] 1062 - 가르침

[문제링크]

1062번: 가르침

 

0. 알파벳은 26자이므로, 32bit int를 사용해 bit-masking으로 등장 정보를 저장한다

 

1. chk변수에는 모든 알파벳 정보를 저장해, 등장하는 알파벳들에 대해서만 검사하도록 한다

 

2. a,n,t,i,c 5자는 반드시 등장하므로, 기본적으로 지워두고 시작한다

 

3. m이 5보다 작으면, 위 5자를 지울수 없으므로 즉시 실패, 아니라면 남은 알파벳의 모든 조합을 구한다

 

4. 모든 가능한 조합에 대해 알파벳을 지워보면, 모든 알파벳이 가르쳐진 단어는 그 값이 0이된다

 

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

public class Main{
	
	static int n,m,chk,max;
	static int[]word;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		word = new int[n];
		//기본으로 지워줘야하는 단어들
		int[]base=new int[] { 1<<'a'-'a', 1<<'n'-'a', 1<<'t'-'a', 1<<'i'-'a', 1<<'c'-'a'};
		
		//bit로 저장
		chk=0;
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < s.length(); j++) {
				word[i] = word[i] | 1<<(s.charAt(j)-'a');
				chk=chk | 1<<(s.charAt(j)-'a');
			}
		}
		
		//기본 5개 삭제
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 5; j++) {
				word[i] = word[i] & ~base[j];
				chk = chk & ~base[j];
			}
		}
		m-=5;
		
		max=0;
		if(m>=0)combi(0,0);
		System.out.println(max);
	}
	
	static void combi(int cnt, int prev) {
		if(cnt>=m || chk==0) {
        	//n개의 단어를 다 가르쳤을때
			int readCnt=0;
			for (int i = 0; i < n; i++) {
				if(word[i]==0)readCnt++;
			}
			max=Math.max(max, readCnt);
			return;
		}
		int[]temp = word.clone();
		int tempchk=chk;
		
		for (int i = prev; i < 26; i++) {
			if( (chk & 1<<i) != 0 ) {
				word=temp.clone();
				chk=tempchk;
				
				chk = chk & (~(1<<i));
				for (int j = 0; j < n; j++) {
					word[j] = word[j] & (~(1<<i));
				}

				combi(cnt+1, i+1);
			}
		}
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면