[백준] 1062_가르침

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

1062번: 가르침

문제

• N과 K과 주어진다.
  • N은 단어, K는 아는 단어이다.
  • 아는 단어를 6개로 지정했을 때 N개의 단어를 몇개 배울 수 있는지 최대 갯수를 출력한다.

풀이

• 아는 단어 중 "anta", "tica"는 반드시 들어간다. 
  
  • "a", "n", "t", "i", "c" 5개의 단어이다.
    • 즉 K가 5이하로 주어지면 배울수 있는 단어는 없다.
    • K=26 이면 모든 단어 가능하다.

코드

• 기본적인 a, n, t, i, c 체크 해주기

 static void beforeCheck(){
        //'a','n','t','i','c'
        alpha2['a' - 'a']  = true;
        alpha2['n' - 'a']  = true;
        alpha2['t' - 'a']  = true;
        alpha2['i' - 'a']  = true;
        alpha2['c' - 'a']  = true;
    }

• dfs 설계
  • cnt == k 일 때 즉, 배울수 있는 단어를 최대로 배운다.
  • 배울 수 있는 단어를 체크한 뒤 가능여부의 max 값을 가져온다.

 static void dfs(int start ,int cnt){
        if(cnt == k){
            int possible = 0 ;
            for(int i = 0 ; i < n; i++){
                boolean flagTrue = true;
                for(int j = 0 ; j < arr[i].length() ; j++){
                    if(!alpha2[arr[i].charAt(j)-'a']){
                        flagTrue = false;
                        break;
                    }
                }
                if(flagTrue == true){
                    possible++;
                }
            }
            max = Math.max(max,possible);
            return ;
        }


        for(int i = start ; i <=26 ; i++){
            if(!alpha2[i]){
                alpha2[i] = true;
                dfs(i,cnt+1);
                alpha2[i] = false;
            }
        }

    }

• 특정 단어 (가운데 단어만 빼서) 검사해서 효율성 올리기

 for(int i = 0 ; i < n ; i ++){
                String tempStr = br.readLine();
                arr[i] = tempStr.substring(4,tempStr.length()-4);
            }
            k  = k - 5;
            beforeCheck();
            dfs(0,0);
            System.out.println(max);
}