[BOJ/백준] 1062. 가르침 (Python)

🔎 문제

🔗 백준 1062번 가르침

💡 풀이

문제를 요약하면,

남극 언어는 앞은 ‘anta’, 뒤는 ‘tica’로 구성되어 있다. K개의 알파벳만 배울 수 있는 상황이다. K개의 알파벳을 어떻게 구성해야 최대한 많은 단어를 배울 수 있을까?

# K가 5보다 작으면 antatica(중복제거->5글자) 도 못배움
if K < 5:
    print(0)
    sys.exit()
# K가 26이면 다 배울수 있음
elif K == 26:
    print(N)
    sys.exit()

• 먼저, ‘anta’, ‘tica’는 무조건 배워야 한다.
• 따라서 ‘a’, ‘c’, ‘i’, ‘n’, ‘t’ 이 다섯 개의 글자는 무조건 배워야 한다. 그러므로 K가 일단 5보다 작으면 아무것도 못배운다. 0을 출력하고 프로그램을 종료한다.
• 알파벳은 26개이다. K가 26이면 N개의 단어를 다 배울 수 있다. 그러므로 N을 출력하고 프로그램을 종료한다.

words = [set(sys.stdin.readline().rstrip()) for _ in range(N)]
learn = [0] * 26
result = 0

• 중복된 알파벳은 제거한다. 파이썬의 set 을 이용하면 된다.
• 알파뱃 갯수인 26을 길이로 갖는 리스트인 learn을 정의한다. 여기에 해당 알파뱃을 배우는지 안배우는지 체크할것이다.

# a, c, i, n, t는 무조건 배워야 함
for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = True

a, c, i, n, t는 무조건 배우고 시작해야 하므로 learn에 체크한다. 그러고 dfs 함수를 호출한다.

def dfs(idx:int, count: int, learn: list, words: list):
    global result
    
    if count == K - 5:
        tmp = 0
        for word in words:
            isContain = True
            for w in word:
                # 한 번이라도 알파벳이 해당 단어에 없으면
                # 배울 수 없다.
                if not learn[ord(w) - ord('a')]:
                    isContain = False
                    break
            if isContain:
                tmp += 1
        result = max(tmp, result)
        return

    for i in range(idx, 26):
        if not learn[i]:
            learn[i] = True
            dfs(i, count + 1, learn, words)
            learn[i] = False

• count가 K - 5일 경우 (K - 5랑 비교하는 이유는 acint는 배웠기 때문)
  • words 리스트를 돌며 단어 하나에 대해 또 for문을 돈다. 단어를 구성하는 알파벳을 하나씩 체크하고 하나라도 learn[알파벳]이 False인 알파벳을 갖고있다면 그것은 못배우는 단어이다.
  • 단어를 구성하는 모든 알파벳이 배운 글자이면 갯수를 세고있는 tmp를 하나 증가시키고, 모든 단어들을 체크한 뒤 max를 구하고 return. dfs종료
• 아직 count가 K - 5가 안되었을 경우엔 learn 리스트에 대해서 dfs를 수행한다. 모든 경우의 수(K개의 글자를 무엇으로 구성 할 것인지)에 대해 위 절차를 반복하게 된다.

📃 소스코드

import sys

def dfs(idx:int, count: int, learn: list, words: list):
    global result
    
    if count == K - 5:
        tmp = 0
        for word in words:
            isContain = True
            for w in word:
                # 한 번이라도 알파벳이 해당 단어에 없으면
                # 배울 수 없다.
                if not learn[ord(w) - ord('a')]:
                    isContain = False
                    break
            if isContain:
                tmp += 1
        result = max(tmp, result)
        return

    for i in range(idx, 26):
        if not learn[i]:
            learn[i] = True
            dfs(i, count + 1, learn, words)
            learn[i] = False

N, K = map(int, input().split())

# K가 5보다 작으면 antatica(중복제거->5글자) 도 못배움
if K < 5:
    print(0)
    sys.exit()
# K가 26이면 다 배울수 있음
elif K == 26:
    print(N)
    sys.exit()

words = [set(sys.stdin.readline().rstrip()) for _ in range(N)]
learn = [0] * 26
result = 0

# a, c, i, n, t는 무조건 배워야 함
for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = True

dfs(0, 0, learn, words)

print(result)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️