1️⃣ 서론
백준 문제 1062번 가르침 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
남극언어의 모든 단어는 “anta”로 시작되고, “tica”로 끝납니다.
남극언어에 단어는 N개 밖에 없다고 가정합니다.
학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하는 문제입니다.
3️⃣ 풀이
남극의 모든 단어는 “anta” 와 “tica”가 들어있기 때문에
기본적으로 알파벳 “a,c,i,n,t” 5개가 들어있습니다.
그러므로 만약 k 가 5보다 작다면 어떤 언어도 배울 수 없습니다.
또한 알파벳 개수는 26개이기 때문에 k 가 26이라면 모든 언어를 배울 수 있습니다.
나머지 경우의 수인 5 <= k < 26 의 경우에는 가장 많은 단어를 배우기 위해
무조건 a, c, i, n, t 는 배웠다고 가정하고 나머지 배울 알파벳을 k-5까지 dfs로 탐색
하며 가장 많은 경우를 검색하면 답을 찾을 수 있습니다.
그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys
n, k = map(int, input().split())
# k 가 5보다 작으면 어떤 언어도 배울 수 없음
if k < 5:
print(0)
exit()
# k 가 26이면 모든 언어를 배울 수 있음
elif k == 26:
print(n)
exit()
answer = 0
words = [set(sys.stdin.readline().rstrip()) for _ in range(n)]
learn = [0] * 26
# 적어도 언어 하나는 배우기위해 a,c,i,n,t 는 무조건 배워야함
for c in ('a', 'c', 'i', 'n', 't'):
learn[ord(c) - ord('a')] = 1
def dfs(idx, cnt):
global answer
if cnt == k - 5:
readcnt = 0
for word in words:
check = True
for w in word:
if not learn[ord(w) - ord('a')]:
check = False
break
if check:
readcnt += 1
answer = max(answer, readcnt)
return
for i in range(idx, 26):
if not learn[i]:
learn[i] = True
dfs(i, cnt + 1)
learn[i] = False
dfs(0, 0)
print(answer)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
