-
[Python 3] BOJ - 1062 "가르침"BOJ 2020. 4. 12. 17:22
# 문제 링크 : https://www.acmicpc.net/problem/1062
# 풀이 :
개인적으로 이 문제의 핵심은 문자열 비교를 비트마스킹으로 하는 것이라고 생각한다. 문제의 조건에 따라 A, C, N, T, I는 필수적으로 들어가야 하므로 총 알파벳 26개 중 21개만 가능한 후보군이 된다. 따라서 만일 K가 5 미만이라면 어떠한 글자도 읽을 수 없다.
만일 K가 5 이상이라면 총 21개 중 K - 5개를 뽑는 조합의 경우와 같다. 여기서 뽑은 조합의 비트마스킹 수에 단어에 해당하는 비트마스킹이 포함되어 있다면 읽을 수 있으므로 각 경우마다 읽을 수 있는 단어 수를 알 수 있고 이것의 최대값을 정답으로 출력하면 된다
위 그림 1은 배열 [a,b,c]의 부분집합을 그림으로 나타낸 것이다. 그런데, 있다 혹은 없다는 2가지 상태로 나타낼 수 있기 때문에 각 원소가 있는지 없는지를 이진수로 표현하고 이를 정수로 바꿔서 생각할 수도 있다. 즉, 어떤 문자의 부분집합을 하나의 정수로 나타낼 수 있기에 훨씬 비교가 빨라진다.
위 그림 2는 실제적으로 각 부분집합의 비교를 나타낸 것이다. 현재 정수 3은 a,b를 포함한 부분 집합이고, 정수 1은 a만 포함한 부분집합이다. 따라서 [a]는 [a.b]에 포함되므로 AND 연산을 통해 1이 나오면 포함되었다고 할 수 있고 0이 나오면 포함되지 않았음을 알 수 있다.
파란색 글자는 위와 아래의 숫자가 같음을 의미하고, 빨간색은 위와 아래의 숫자가 같지 않음을 의미한다. AND 연산은 위아래가 같은 숫자라면 그 숫자를 그대로 취하고, 같지 않다면 0으로 나타내는 연산이다.
# 코드
import sys, itertools # n, m 입력 n,m = map(int, sys.stdin.readline().split()) # words : 각 단어의 비트마스킹한 정수를 저장 words = [0] * n ans = 0 for i in range(n): temp = sys.stdin.readline().rstrip() # word 배열에 각 문자의 비트마스킹 저장 for x in temp: words[i] |= (1 << (ord(x) - ord('a'))) # 만일 m이 5미만이면 필수 글자를 다 배울 수 없기 때문에 한 단어도 읽지 못한다 if m < 5: print(0) else: # candidiate : 필수 글자를 제외한 알파벳 # need : 필수 알파벳 candidiate = ['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z'] need = ['a','c','t','i','n'] for i in list(itertools.combinations(candidiate, m - 5)): each = 0 res = 0 # 각 조합에 대한 비트마스킹 for j in need: each |= (1 << (ord(j) - ord('a'))) for j in i: each |= (1 << (ord(j) - ord('a'))) # 단어와 각 조합의 비교 for j in words: if each & j == j: res += 1 # 최대값 갱신 if ans < res: ans = res print(ans)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1080 "행렬" (0) 2020.04.14 [Python 3] BOJ - 1074 "Z" (0) 2020.04.14 [Python 3] BOJ - 1016 "제곱 ㄴㄴ수" (0) 2020.04.09 [Python 3] BOJ - 1024 "수열의 합" (0) 2020.04.08 [Python 3] BOJ - 1002 "터렛" (0) 2020.04.07