BOJ 10160 암호

암호

(http://boj.kr/10160)

ABCBC 또는 ABABC가 포함되지 않도록 암호를 만들어야 한다.

이 부분에서 아이디어를 얻어, 암호를 끝자리에 따라서 분류해서 불가능한 암호를 안 만들도록 한다.

ABCBC를 안 만들기 위해서는, 끝 자리가 ABCB일 때 C를 안 붙이면 된다.

ABCB인 경우를 알기 위해선 ABC인 경우에서 B를 붙이면 된다.

ABC인 경우를 알기 위해선 AB인 경우에서 C를 붙이면 된다.

...

이런 식으로 경우를 나눠보면,

d[i][j]를 j번 경우로 끝나는 i자리 암호라고 했을 때,

0번 경우 -> ABCB로 끝나는 경우

1번 경우 -> ABC로 끝나는 경우

2번 경우 -> AB로 끝나는 경우

3번 경우 -> A로 끝나는 경우

4번 경우 -> ABAB로 끝나는 경우

5번 경우 -> ABA로 끝나는 경우

6번 경우 -> 그 외의 경우

로 나눌 수 있다.

이 때, 2번 경우와 4번 경우처럼 겹치는 경우에는 더 긴 경우를 우선적으로 겹치지 않게 세야 한다.

식을 세우면,

d[1][0, 1, 2, 4, 5] = 0, d[1][3] = 1, d[1][6] = k - 1이고,

d[i][0] = d[i - 1][1]

d[i][1] = d[i - 1][2]

d[i][2] = d[i - 1][3]

d[i][3] = d[i - 1][0] + d[i - 1][1] + d[i - 1][3] + d[i - 1][5] + d[i - 1][6]

d[i][4] = d[i - 1][5]

d[i][5] = d[i - 1][2] + d[i - 1][4]

d[i][6] = d[i - 1][0] * (k-2) + d[i - 1][1] * (k-2) + d[i - 1][2] * (k-2) + d[i - 1][3] * (k-2) + d[i - 1][4] * (k-2) + d[i - 1][5] * (k-2) + d[i - 1][6] * (k-1) 

으로 된다.

#include <bits/stdc++.h>
 
const long long r = 1000000009;
 
long long d[1000001][7];
 
int main() {
    long long n, k, ans = 0;
 
    scanf("%lld %lld", &n, &k);
 
    d[1][3] = 1;
    d[1][6] = k - 1;
 
    for (int i = 2;i <= n;++i) {
        d[i][0] = d[i - 1][1];
        d[i][1] = d[i - 1][2];
        d[i][2] = d[i - 1][3];
        d[i][3] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][3] + d[i - 1][5] + d[i - 1][6]) % r;
        d[i][4] = d[i - 1][5];
        d[i][5] = (d[i - 1][2] + d[i - 1][4]) % r;
        d[i][6] = ((k - 1) * d[i - 1][6] + (k - 2) * (d[i - 1][0] + d[i - 1][1] + d[i - 1][2] + d[i - 1][3] + d[i - 1][4] + d[i - 1][5])) % r;
    }
 
    for (int i = 0;i < 7;++i)
        ans = (ans + d[n][i]) % r;
 
    printf("%lld", ans);
 
    return 0;
}