hint

1)O(K^NN)

K 개의 알파벳으로 길이 N 인 문자열들을 모두 구한 뒤, 패턴 “ABABC”, “ABCBC”이 나타 나는지 확인하여, 가능한 암호의 개수를 세는 방법이다. 이 방법으로 문제를 해결할 시 10% 의 점수를 받을 수 있다.

2)O(NK⁵)

동적계획법으로 해결 가능하다. 아래와 같이 2차원 배열 D 를 정의한다.

Dip = 길이가 i인 유효한 암호문이며 문자열 뒤 네 글자가 p인 문자열의 개수

정의에 따라 p는 길이가 4인 문자열이다. 뒤에 K 개 종류의 알파벳을 넣어 “ABABC”나 “ABCBC”가 되는지 확인하고, 패턴이 나오지 않은 경우 Di+1 p'에 Dip를 더해주면 된다.

여기서, p′는 문자열 p에 새로 알파벳을 하나 뒤에 붙인 문자열의 뒤 네 글자로 구성 된 문자 열이다. 이 방법으로 문제를 해결할 시 50%의 점수를 받을 수 있다.

3)O(N * 4^5)

O(N*K^5) 방법과 유사한 동적계획법으로 해결한다.

다만 정의의 문자열 p에서 K 개 종류 알파벳을 모두 사용하는 것이 아니라, 네 종류의 알파벳을 사용하며 문제를 해결할 수 있다. 이 방법으로 문제를 해결할 시 90%의 점수를 받을 수 있다.

4) O(N)

위에서 설명한 방법에서 뒤 네 글자를 동적계획법의 상태로 가지고 있다.

이는 4^4= 256 가지의 상태를 가지고 있는 것인데, 여기서 상태의 개수를 7개로 줄일 수 있다.

Di state = 길이가 i인 유효한 암호문이며 현재 상태가 state인 문자열의 개수

state들의 이동은 아래 그림에 의해 설명된다.

점화식에 대한 자세한 설명은 첨부된 모범코드를 참고한다.

5) lg(N)

추가적으로 효과적인 방법으로는 O(N)의 점화식을 행렬 곱셈식으로 표현한 뒤, repeated squaring으로 O(lgN)에 계산하는 방법이 있다.