[백준] 1062번: 가르침 (python)

www.acmicpc.net/problem/1062

1062번: 가르침

import sys
from itertools import combinations

def set2bit(string_set):
    bit = 0
    for s in string_set:
        bit |= 2**(ord('z')-ord(s))
    return bit

def make_candidate(word):
    candidate = set()
    for w in word:
        candidate |= w
    return candidate

if __name__ == '__main__':
    default = set("anta") | set("tica")

    N, K = map(int, sys.stdin.readline().split())
    word = [set(sys.stdin.readline().strip())-default for _ in range(N)]

    if K < len(default):
        print(0)
    else:
        candidate = make_candidate(word)
        if len(candidate) <= K-len(default):
            print(N)
        else:
            binary =[set2bit(w) for w in word]
            cnt = 0
            for comb in combinations(candidate, K-len(default)):
                tmp = 0
                c = set2bit(set(comb))
                for b in binary:
                    if b & ~c == 0:
                        tmp += 1
                cnt = max(cnt, tmp)
            print(cnt)

 

 

 

 

문제 해석 : 소문자 a~z 중 K개의 알파벳을 가르쳐서, N개의 단어 중 읽을 수 있는 최대 개수를 출력합니다.

 

default = {'a', 'i', 't', 'c', 'n'}로, 이 중 한 개의 알파벳이라도 가르치지 않으면

글자를 읽을 수 없습니다.

    if K < len(default):
        print(0)

 

default를 제외한 모든 word의 합집합인 candidate의 개수가 K-len(default)보다 작거나 같으면

모든 N개의 글자를 읽을 수 있습니다.

        if len(candidate) <= K-len(default):
            print(N)

 

default를 제외한 word(b)가

candidate에서 K-len(default)개를 순서에 관계없이 선택(c)한 것의 부분집합일 경우,

그 해당 단어를 읽을 수 있습니다.

                for b in binary:
                    if b & ~c == 0:
                        tmp += 1

 

위를 계산하기 위해 비트 연산을 이용하였으며(b & ~c),

비트 표현은 'a'=2^25부터 'z'=2^0으로 표현하였으며,

def set2bit(string_set):
    bit = 0
    for s in string_set:
        bit |= 2**(ord('z')-ord(s))
    return bit

 

각 비트에 대해 원하는 비트 계산식은 다음과 같습니다.

b	0	0	1	1
c	0	1	0	1
결과	0	0	1	0

 

 

그리고 카르노맵을 이용하여 b & ~c 조건을 만들어 내어

b & ~c == 0일 경우, b가 c의 부분집합이 됩니다.

	~b	b
~c	0	1
c	0	0