Baekjoon 9997. 폰트 / Python

9997. 폰트

난이도 : 골드 3
소요 시간 : 30분
날짜 : 2025.01.10
언어 : 파이썬
알고리즘 유형 : 비트마스킹, 완전탐색, 재

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 단어들이 주어진다.
2. 단어들을 조합해서 문장을 만든다.(중복X, 순서X)
3. 모든 알파벳이 포함되는 문장의 개수를 구한다.

2. 해결 방식

1. 단어를 비트로 바꾸어 저장한다.
   • 목표 goal = (1 << 26) - 1 이 된다.
2. 재귀함수 + 완전탐색 : sol(bit, idx)
   • idx를 0부터 시작해서 하나씩 늘려가면서 확인한다.
   • 종료조건 1 : 현재 bit가 goal에 도달하면 남은 단어들의 모든 경우의 수 $2^(n - idx)$ 를 반환하고 종료
   • 종료조건 2 : idx가 n이 되면 0을 반환하고 종료
   • 재귀 : 현재 idx에 해당하는 단어를 넣는 함수 호출, 안넣는 함수 호출
3. memoization : 시간을 1/3으로 줄였다. 압도적으로 시간 1등을 하게 해준 시간 최적화
   • 딕셔너리를 만든다 key : (비트, idx), value : 경우의 수
   • 딕셔너리를 분기 조건으로 만든다.

3. 정답 코드

import sys
# input = sys.stdin.readline
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

n = int(input())
arr = [input().strip() for _ in range(n)]
arr_bit = [0] * n

for i in range(n):
    char = arr[i]
    for s in char:
        arr_bit[i] |= 1 << (ord(s) - 97)

res = 0
goal = (1 << 26) - 1
dp = {}
def sol(now_bit=0, idx=0):
    key = (now_bit, idx)
    if key in dp:
        return dp[key]
    if now_bit == goal: 
        return 2 ** (n - idx)
    if idx >= n:
        return 0

    res = sol(now_bit, idx + 1) + sol(now_bit | arr_bit[idx], idx + 1)
    dp[key] = res
    return res

print(sol())