알고리즘/백준

1062 가르침

아메숑 2019. 3. 6. 21:15
1. 문제




2. 코드

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
def dfs(cnt,learn,index):
    global maxval
    if index > 26:
        return
    if cnt == K:
        total = 0
        for i in range(N):
            t = word[i]
            ok = True
            for j in range(len(t)):
                if (1<< ord(t[j])-97) & learn != 0:
                    continue
                ok = False
                break
            total += int(ok)
        maxval = max(maxval,total)
        return
    #만약 인덱스가 a,n,t,i,c라면
    if index == 0 or index == 2 or index == 8 or index == 13 or index == 19:
        dfs(cnt,learn,index+1)
    else:
        #배울경우
        dfs(cnt+1,learn|(1<<index),index+1)
        #배우지 않을 경우
        dfs(cnt,learn,index+1)
 
 
N, K =map(int,input().split())
K -= 5
word = [input() for _ in range(N)]
index = 0
#a,n,t,i,c은 이미 배운것으로 처리
index |= (1<< (ord('a')-97))
index |= (1<< (ord('n')-97))
index |= (1<< (ord('t')-97))
index |= (1<< (ord('i')-97))
index |= (1<< (ord('c')-97))
maxval = -1
dfs(0,index,0)
print(maxval)
 
cs

3. 후기
처음에는 문자열 배열을 받은 다음에 'a,n,t,i,c'를 없앤 배열을 만든 후 남은 글자를 set으로 받아서 중복을 없앤 뒤 백트랙킹으로 풀었다. 하지만 시간초과가 나서 비트마스킹을 이용해서 이미 배운 글자를 구분하였다. 하지만 또 시간초과가 났다. 파이썬으로는 풀 수 없는 문제인 것 같다. 하지만 비트마스킹을 배우기 좋은 문제같다.