[백준]1062: 가르침 - JAVA

[백준]1062: 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

풀이

백트래킹과 조합을 사용하여 풀었다.

 

이 문제는 앞 뒤 'anta'와 'tica'에 속한 a,c,n,t,i 5개의 알파벳을 제외하고 k개의 알파벳을 추가로 학습하여 읽을 수 있는 단어의 최대 개수를 구하는 문제이다.

 

알파벳을 뽑았는지 확인하기 위해 boolean타입의 visited배열을 선언해 주었고 이미 알고있는 a,c,n,t,i를 true로 설정해 주었다. 그리고 뽑은 알파벳들을 true로 바꾼 후 조건에 맞는 수의 알파벳을 다 뽑고 난 후 읽을 수 있는 단어의 개수를 계산해 주었다.

 

이때 a,c,n,t,i가 이미 5개의 알파벳이므로 k가 5개 이하의 개수가 들어온다면 읽을 수 있는 단어의 개수가 없다.

그리고 k가 26이 입력된다면 모든 알파벳을 읽을 수 있다는 의미이므로 n을 반환해 주면 된다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n, k;
    static int max = Integer.MIN_VALUE;
    static boolean[] visited;
    static String[] word;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        k = scan.nextInt();
        
        scan.nextLine();
        word = new String[n];
        for(int i = 0; i < n; i++) {
            String str = scan.nextLine();
            str = str.replace("anta", "");
            str = str.replace("tica", "");
            word[i] = str;
        }
        
        if(k < 5) { //a c i n t의 개수가 5개이므로
            System.out.println("0");
            return;
        } else if(k == 26) { //모든 알파벳을 다 읽을 수 있다.
            System.out.println(n);
            return;
        }
        
        visited = new boolean[26]; //각 알파벳을 배웠는지 체크
        visited['a' - 'a'] = true;
        visited['c' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        
        backtracking(0, 0);
        System.out.println(max);
    }
    
    public static void backtracking(int alpha, int len) {
        if(len == k - 5) {
            int count = 0;
            for(int i = 0; i < n; i++) { //뽑은 알파벳으로 몇개의 단어를 읽을 수 있는지 카운트.
                boolean read = true;
                for(int j = 0; j < word[i].length(); j++) {
                    if(!visited[word[i].charAt(j) - 'a']) {
                        read = false;
                        break;
                    }
                }
                if(read) count++;
            }
            max = Math.max(max, count);
            return;
        }
        
        for(int i = alpha; i < 26; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                backtracking(i, len + 1);
                visited[i] = false;
            }
        }
    }
}