문제 링크
문제
새로 바뀐 KOI 웹사이트의 암호는 N개의 영문 알파벳 대문자로 이루어진다. 특별히 암호는 영문 알파벳 중 처음 K개를 사용해서 만든다. 예를 들어, K=5이면, ‘A', 'B', 'C', 'D', 'E'만으로 암호를 만들게 된다. 하지만 문자가 중복되어 나타날 수도 있고 전혀 안 나타날 수도 있다.
최근 연구에 의해서 2가지의 특정 패턴이 암호에 상당히 많이 나타난다는 사실이 알려졌다. 이 특정 패턴은 ABCBC 와 ABABC 이다. 해커들이 이 정보를 이용할 수 있기 때문에 암호를 만들 때 이 두 패턴 중 어떤 것도 암호 안에 나타나는 것을 피하는 것이 안전한 암호를 만드는 방법이 될 수 있다. 따라서 위의 패턴이 나타나지 않는 암호를 안전한 암호라고 부르고, KOI 웹사이트는 사용자들이 안전한 암호만을 사용하도록 결정하였다.
예를 들어, N=6, K=3일 때, 위 패턴을 포함하는 암호들은 다음과 같은 12가지가 있다.
- ABCBCA, ABCBCB, ABCBCC, AABCBC,
- BABCBC, CABCBC, ABABCA, ABABCB,
- ABABCC, AABABC, BABABC, CABABC
가능한 총 암호의 개수 36 = 729에서 위의 12가지를 제외하면 717가지의 안전한 암호를 만들 수 있다.
암호의 길이 N, 문자의 가지 수 K가 주어질 때, 만들 수 있는 안전한 암호의 총 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄에는 각각 암호의 길이와 문자의 가지 수를 나타내는 정수 N 과 K가 공백을 사이에 두고 주어진다. 이 두 정수 값의 범위는 5 ≤ N ≤ 1,000,000, 3 ≤ K ≤ 26이다.
출력
출력은 한 줄로 이루어진다. 안전한 암호의 총 개수를 1,000,000,009으로 나눈 나머지를 출력한다. 계산 과정에서 32비트 정수 변수가 표현할 수 있는 범위를 넘어서 64비트 정수 변수를 사용해야 할 수도 있음에 주의하라.
풀이
안전한 암호의 총 개수(answer)를 출력해야 한다.
- N=1 일 때 answer은 K개 다.
- N=2 일 때 answer은 K x K개다.
- N=3 일 때 ...
...
-
N=5 일 때를 보면
ABCBC, ABABC 패턴이 최초로 나오는 지점이다.
그래서 K^5에서 - 2를 하면 answer이 된다. -
N=6 일 때를 보면
x x x x x / O
N=5일 때에서 한 자리(O)가 추가된 경우다. 이 자리는 맨 뒤라고 생각해도 상관 없다. 어차피 다른 자리에서 가능한 경우는 똑같기 때문이다.
그러면 가능한 경우의 수는 dp[5] x K가 된다.
그런데 생각해보면 다음과 같은 경우는 패턴이 생기기 때문에 그 경우를 빼줘야 한다.
x x A B C B / C,
x x A B A B / C
그래서 dp[i - 5] x 2를 빼준다. (x x일 때 안전한 암호의 개수는 dp[2]이기 때문이다.)
...
- 마지막으로 N=9 일 때를 보자,
x x x x x x x x / O
이 경우도 dp[8] x K - (dp[i - 5] x 2)를 빼줘야 한다.
그런데 또 패턴이 나오는 경우가 있다.
x x A B/ A B C B / C 여기서 A B A B C가 중간에 나오는 것을 볼 수 있다.
그러니까 단순히 dp[i - 5]는 x x A B를 포함하기 때문에 A B C B / C와 결합하면서 패턴의 경우의 수가 들어간다.
그래서 dp[i - 5] (x x x x)에서 (x x A B)를 빼줘야 한다.
(x x A B)는 dp[i - 7]개 이기 때문에 이 값을 빼주면 된다.
여기서...x x와 A B의 결합은 신경쓰지 않아도 된다. 왜냐하면 어떠한 경우에도 패턴을 만들어내지 못하기 때문이다.
이를 토대로 점화식을 도출하면,
dp[i] = dp[i - 1] x K - (dp[i - 5] x 2);
여기서 i가 7보다 크거나 같으면 추가적으로 dp[i] = dp[i] + dp[i - 7]; 해주면 된다.
(여기서 dp[0]은 1로 가정한다.)
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static final int MOD = 1000000009;
static int N,K;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
long[] dp = new long[N + 1];
dp[0] = 1;
for(int i=1; i<=4; i++) {
dp[i] = (dp[i - 1] * K) % MOD;
}
for(int i=5; i<=N; i++) {
dp[i] = (dp[i - 1] * K) % MOD;
dp[i] = (dp[i] - dp[i - 5] * 2 + MOD + MOD) % MOD;
if(i >= 7) {
dp[i] = (dp[i] + dp[i - 7]) % MOD;
}
}
System.out.println(dp[N]);
}
}