글 읽기 - 시간초과가 왜 나는지 모르겠네요(비트마스킹)

dmsrud1618 2년 전 0

도대체 어느 코드가 시간이 오래걸리게 하는지 모르겠네요

지적 부탁드립니다!!..

from itertools import combinations
n,k = map(int,input().split())
if k-5>0:
  lr=set("antci")
  vl=[] #단어당 필요한 문자의 합
  p=[] #필요한 단어 비트
  x=0 #안배워도 읽을 수 있는 단어 개수
  t={b:a for a,b in enumerate(set(map(chr, range(ord("a"),ord("z")+1)))-lr)}
  for i in range(n):
    tp=0
    for j in set(input()[4:-4])-lr:
      a=1<<t[j]
      tp|=a
      p.append(a)
    if tp==0:
      x+=1
    else:
      vl.append(tp)
  m=x
  for i in combinations(p,k-5):
    s=sum(i)
    ct=x
    for j in vl:
      if s&j==j:
        ct+=1
    m=max(m,ct)
  print(m)
else:
  print(0)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 왜 나는지 모르겠네요(비트마스킹)

dmsrud1618 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말