[비트마스킹 / 파이썬] 백준 9997번: 폰트 / 골드 2

https://www.acmicpc.net/problem/9997

9997번: 폰트

import sys
sys.setrecursionlimit(10**5)
n = int(input())

lst = []
for _ in range(n):
    word = input()
    b = 0
    for alpha in word:
        order = ord(alpha)-ord('a')
        b |= 1 << order
    lst.append(b)

def recursion(idx, used, double):
    global answer

    #pruning
    if bin(used)[2:].count('1') == 26:
        answer += 2**(n-idx+double)
        return

    if idx == n:
        return

    union = used | lst[idx]

    if used == union:
        recursion(idx+1, used, double + 1)
    else:
        recursion(idx + 1, used, double)
        recursion(idx+1, union, double)


answer = 0
recursion(0, 0, 0)
print(answer)

풀이 방법

n의 제한이 25이기 때문에 브루트포스로 접근해도 충분히 풀이가 가능하다.

다만 테스트를 해보니 가지치기를 적절히 해주지 않으면 타임아웃이 발생하였다.

 

비트마스킹 이용

<< 쉬프트 연산을 이용하여 b의 비트의 원하는 자리에 1을 집어넣을 수 있다.

| 유니온 연산을 이용하여 used 비트에 lst[idx]의 1 비트를 채워넣어 준다.

 

pruning(가지 치기) - 문제 해결의 핵심

알파벳을 모두 모은 상태가 되면 탐색을 종료해도 된다. 단, answer에 1을 더해주는 걸로 실수하면 안된다. 아직 탐색하지 않은 문자들은 포함/비포함 상관이 없기 때문에 모든 경우의 수인 2**(탐색 안한 개수)을 더해줘야 한다.

 

기존 used의 상태와 lst[idx]의 상태를 union한 결과가 동일하다면, 굳이 2가지로 분기해줄 필요가 없다. 어차피 이후에도 계속 동일한 양상(?)을 띌 것이기 때문이다. 다만 분기를 하지 않는다는 사실 자체는 갖고 있어야 나중에 answer 값을 똑바로 계산할 수 있다. 나는 이를 위해 double 파라미터를 추가했다.

 

평가

풀이에 오랜 시간이 걸린 이유는 시간 초과를 해결하지 못해서다.

가지 치기 2번째 항목을 파악하는 데 좀 걸렸다.