백준 1062 가르침

문제 분석

a~z까지 알파벳을 공부하고 입력단어를 만들 수 있는지 확인하는 문제입니다. 알파벳 공부개수를 제한시키는 제약이 있습니다. 그리고 제약조건에 단어는 "anta"로 시작하고 "tica"끝난다고 되어 있으니, "a", "c", "i", "n", "t" 총 5개 알파벳은 무조건 공부 해야 합니다.

 

첫 번째 예제를 분석해볼게요.

3 6
antarctica
antahellotica
antacartica

 

K가 6개이므로 미리 학습해야 하는 5개를 제외하면 1개 알파벳만 추가공부할 수 있습니다. 따라서 1, 3번째 단어만 공부할 수 있습니다.

anta rc    tica -> r 추가 공부
anta hello tica -> h, e, l, o 추가 공부
anta car   tica -> r 추가 공부

 

푸는 방향

1. 시간복잡도는 2^26이면서 알파벳 중복 공부를 제외하는 방법을 찾아야합니다. 비트 연산은 중복 검사 무시에 매우 적합합니다. 그리고 시간복잡도도 2^30미만이어서 시간초과가 안될 확률이 높습니다.

# 초기 값
a = 1

# 2번 or 연산
a |= 1
a |= 1

# 1이 포함되어 있는지 확인
print(a & 1)

 

2. 검사로직은 비트연산로 결정되었습니다. 남은 로직은 검사로직에 넘길 인자를 어떻게 만들 것인가입니다. a~z까지 알파벳을 공부할 때 경우의 수는 2개입니다. 

1. 특정 알파벳을 공부했거나

2. 특정 알파벳을 공부안했거나 

 

공부했거나 안했거나를 이용하면 마치 이진트리처럼 경우의수가 나눠집니다. 트리의 높이는 공부의 끝에 해당하고 알파벳 z순서인 26에 해당합니다.

 

수도 코드(파이썬)는 아래와 같습니다.

# 수도코드

def check(mask: int):
  cnt = 0
  for word in words:
    # 비트 and연산
    cnt += (word & mask) == word
  return cnt

def solve(index: int, study_count: int, mask: int):  
  # 공부 회수가 0미만이면 단어공부 실패
  if study_count < 0:
    return 0
 
  # 알파벳 'z'까지 공부한 경우 단어공부 가능한지 확인
  if index > 26:
    return check(mask)
  
  # 공부 (트리 왼쪽방향)
  answer = solve(index+1, study_count-1, mask | (1 << index))
  if "a", "c", "i", "n", "t"에 속하지 않으면:
    # 공부하지 않음 (트리 오른쪽방향)
    t = solve(index+1, study_count, mask)
    answer = max(answer, t)
  
  return answer

 

참고자료

인프런 큰돌님 강의