문제

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

3가지 풀이

재귀를 통한 완전탐색 (백트래킹)

point

• 탈출조건
  • 세팅한 키의 개수가 n개 모두 완료된 경우
    : 퀘스트 클리어 가능 개수 연산 후 max값 최신화
  • 스킬 2n개 탐색 완료
    : 종료
• 발생 할 수 있는 모든 경우에 대해 재귀 진행
  • 현재 스킬 키세팅 안 하고 다음 스킬로 넘어감
  • 현재 스킬 키세팅에 추가하고 다음 스킬로 넘어감
• set을 이용해 세팅된 스킬과 퀘스트에 필요한 스킬 구성 비교
  : 부분집합
  • set1 <= set2
    : set1이 set2의 부분집합이면 True 리턴

전체 코드

kn, qn, qsn = [int(x) for x in input().split()]

qs = []
for i in range(qn):
  s = set([int(x) for x in input().split()])
  qs.append(s)

def clear_num(s):
  num = 0
  for a in qs:
    if a <= s:
      num+=1
  return num

max_clear = 0
def step(s, i, sl):
  global max_clear, kn
  if i > 2 * kn:
    return 
  step(s, i+1, sl)
  new_s = s.copy()
  new_s.add(i)
  sl += 1
  if sl == kn:
    clear = clear_num(new_s)
    max_clear = max(max_clear, clear)
    # print(f"{new_s} - {max_clear}")
    return
  step(new_s, i+1, sl)

s = set()
step(s, 1, 0)
print(max_clear)

combination 라이브러리 함수를 이용

point

• 완탐 재귀를 통해 키세팅의 모든 경우의수에 대해 퀘스트 클리어 개수를 최신화 했던 이전 방법과 달리
• comination 라이브러리 함수를 통해 모든 키세팅 경우의 수를 구해놓고, 하나씩 퀘스트 클리어 개수 연산하면서 max값 도출

전체 코드

from itertools import combinations
        
kn, qn, qsn = [int(x) for x in input().split()]

qs = []
for i in range(qn):
  s = set([int(x) for x in input().split()])
  qs.append(s)

def clear_num(s):
  num = 0
  for a in qs:
    if a <= s:
      num+=1
  return num
    
comb = list(combinations(list(range(1,2*kn+1)), kn))

max_clear = 0
for a in comb:
  clear = clear_num(set(a))
  max_clear = max(max_clear, clear)
print(max_clear)

비트마스크 이용

point

• set 대신 비트마스크를 이용하여 퀘스트에 필요한 스킬과 키세팅된 스킬을 관리
• n번째 bit 추가
  : b |= (1 << n)

전체 코드

kn, qn, qsn = [int(x) for x in input().split()]

qs = []
for i in range(qn):
  s = [int(x) for x in input().split()]
  b = 0
  for a in s:
    b |= (1 << a)
  qs.append(b)

def clear_num(s):
  num = 0
  for a in qs:
    if s & a == a:
      num+=1
  return num

max_clear = 0
def step(s, i, sl):
  global max_clear, kn
  if i > 2 * kn:
    return 
  step(s, i+1, sl)
  s |= (1 << i)
  sl += 1
  if sl == kn:
    clear = clear_num(s)
    max_clear = max(max_clear, clear)
    return
  step(s, i+1, sl)

s = 0
step(s, 1, 0)
print(max_clear)

결과

역순 : 비트마스크 사용 시 시간 가장 많이 단축