백준 1062 가르침

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

N개의 단어가 주어지고, K개의 알파벳을 학습하여 최대 몇 개의 단어를 학습할 수 있는지 구하는 문제이다.

특이한 점이 있다면 모든 단어가 anta로 시작하고 tica로 끝난다는 점이다.

내가 생각한 풀이 방법은 a부터 z까지의 알파벳들 중 K개를 조합으로 선택하여 학습했다 가정하고, 각 선택에 대한 학습 단어 개수를 구해 최댓값을 구하는 것이었다.

하지만 미리 말했듯이 anta와 tica는 모든 단어에 들어가므로 'a', 'n', 't', 'i', 'c' 5개의 문자는 반드시 선택해야 한다.

따라서 총 26 - 5 = 21개의 알파벳 중 K - 5개를 조합으로 선택하여 모든 케이스를 구하면 된다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, K) = readLine().split(' ').map{it.toInt()}
    val words = Array(N){readLine()}
    val ck = BooleanArray(26){false}

    val passive = listOf('a' - 'a', 'n' - 'a', 't' - 'a', 'i' - 'a', 'c' - 'a')
    passive.forEach { ck[it] = true }

    var answer = 0

    fun combination(start: Int, target: Int){
        if(target < 0) return

        if(target == 0){
            var cnt = 0
            for(word in words){
                if(canStudy(word, ck))
                    cnt++
            }
            if(answer < cnt) answer = cnt
        }else{
            for(i in start until ck.size){
                if(passive.contains(i)) continue

                ck[i] = true
                combination(i + 1, target - 1)
                ck[i] = false
            }
        }
    }
    combination(0, K - 5)

    print(answer)
}

fun canStudy(word: String, selected: BooleanArray): Boolean{
    for(c in word){
        if(!selected[c - 'a'])
            return false
    }
    return true
}

효율성을 위해 알파벳을 선택했다는 정보를 BooleanArray로 저장하고, 각 알파벳을 'a'를 빼줌으로써 인덱스로 다루었다.

26개의 알파벳 중 기본으로 가져야 하는 5개의 위치에 미리 true를 입력해 두었다.

그리고 조합 함수를 통해 K - 5개를 뽑는데, 기본으로 가지는 알파벳의 위치는 continue로 넘겨 무시하고 뽑을 수 있도록 하였다.

학습 여부를 구하는 로직은 canStudy 함수를 만들어 각 단어에 해당하는 인덱스(a는 0, c는 2)가 true인지 확인하도록 하였다