Google Kickstart 2018 Round H, Problem A

A. Big Buttons

N (1 ~ 50) R과 B로 구성된 문자열의 자리수
P (min(2^N, 100)) 유효하지 않은 접두사 문자열 개수
유효한 문자열의 개수를 구하는 문제.
ex )
2 1
R
(1) N이 2이므로 RR, RB, BR, BB가 모든 경우
(2) RR, RB를 제외
return 3

Input

3 (N) 2 (P)
BBB
RB

solve

• BR 이 존재하면 BRB, BRBRBB 등은 불필요
• Trie 자료구조를 이용하면 O(NP)만에 중복 문자열에 대한 구분이 가능
• 구하고자 하는 경우의 수는 2^N - sigma(2^(N-length)) 와 같다.

code

​