BOJ-1062 가르침

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

문제 소개

단어의 개수 n과 선생님이 학생들에게 가르칠 글자의 개수 k가 주어진다.

학생들이 읽을 수 있는 단어의 최댓값을 구한다.

모든 단어는 “anta”로 시작하고, “tica”로 끝난다.

문제 풀이

단어를 읽고자 할 때 글자를 배웠는지 여부만 따지면 되므로, 배운 글자와 단어를 set으로 저장하도록 하였다.

그리고 학생들이 배운 글자의 집합은 learned로 선언하여, 진행 과정에서 새로 배운 글자가 추가되게 하였다. 초기값은 a, n, t, i, c이다.

모든 단어에는 a, n, t, i, c 이 무조건 포함되므로, k가 5 미만이라면 어떤 단어라도 읽을 수 없다.

그 점에서 k - 5를 remaining이라는 변수로 선언하여 그 값이 양수, 음수 또는 0인 각각의 경우로 나누어 생각해 보았다.

먼저 remaining이 0인 경우는 a, n, t, i, c 만으로만 이루어진 단어만을 읽을 수 있다.

# a, n, t, i, c 만으로만 이루어진 단어의 개수 출력
arr = list(map(lambda x: x - learned, arr))
print(arr.count(set()))

다음으로 remaining이 음수인 경우는 아무 단어도 읽을 수 없음을 뜻하므로 단순히 0을 출력한다.

print(0)

마지막으로 remaining이 양수인 경우는 학생들이 초기 learned 외에 remaining개의 글자를 배울 수 있음을 의미한다.

필자가 처음 본 문제의 풀이를 시도했을 때는 그리디한 방법을 시도했으나 풀리지 않았고, 배울 글자를 브루트포스로 찾아내는 과정이 필요함을 깨달았다.

다만, 모든 알파벳을 조사할 필요는 없이 각 단어에 속한 단어들의 집합만 구하면 될 것이다.

그를 위하여 집합 cand를 선언하여 각 단어에서 학습을 필요로 하는 글자를 저장하였다.

여기서 만약 구한 cand의 길이가 remaining보다 작거나 같다면 이것은 모든 단어를 읽을 수 있게 할 정도로 k가 여유롭다는 것을 의미하므로, 단순히 단어의 개수인 n을 출력한다.

그렇지 않은 경우, combinations(조합)를 통해 cand내에서 글자를 remaining만큼 골라서 배울 수 있는 각각의 경우에서 읽을 수 있게되는 단어의 수의 최대값을 구한다.

코드

from sys import stdin
from itertools import combinations
input = lambda: stdin.readline().rstrip()

n, k = map(int, input().split())

# 단어를 읽기 위한 필수 글자들
learned = {"a", "n", "t", "i", "c"}
arr = [set(input()) for _ in range(n)]

# 초기 learned 외에 k - 5 개의 알파벳을 선택할 수 있다.
remaining = k - 5
if remaining > 0:
    # cand : 학습을 필요로 하는 글자들의 집합
    cand = set()
    for i in arr:
        cand |= i - learned
    # 모든 단어를 읽을 수 있게 될 정도로 k가 여유로운 경우
    if len(cand) <= remaining:
        print(n)
    else:
        # 조합을 통해 읽을 수 있는 단어의 최댓값 구하기
        answer = 0
        for i in map(set, combinations(cand, remaining)):
            t = learned | i
            cnt = [j - t for j in arr].count(set())
            if answer < cnt:
                answer = cnt
        print(answer)
elif remaining == 0:
    # a, n, t, i, c 만으로만 이루어진 단어의 개수 출력
    arr = list(map(lambda x: x - learned, arr))
    print(arr.count(set()))
else:
    # 아무 단어도 읽지 못함
    print(0)