백준 10160 암호

출처: https://www.acmicpc.net/problem/10160 

dp 점화식은

dp[i]=k*dp[i-1]-dp[i-5]*(long long)2+dp[i-7]

dp[i-5]*2만 빼주면 안된다.

왜냐면 ABABCB_의 _에 C가 들어가는 경우도 빼주는 건데,

dp[i-5]에는 ABABCB로 끝나는 문자열이 애초에 있을 수가 없다!! (안전한 암호의 개수만 저장하는 거니까)

근데 내가 문제였던 건 이게 아니었고... %1000000009를 해주므로 dp[i]가 음수가 될 수 있다.

출력은 무조건 양수므로 <0이면 +1000000009 해야 된다.

이걸로 틀렸습니다 4개 뜸... 허무해

#include<stdio.h>
long long n,k;
long long dp[1000010];
 
long long int dy[1000010][10], f[10][10];
 
 
long long pow(long long a,long long b)
{
    long long tot=1;
    while(b--)
    {
        tot*=a;
        tot%=(long long)1000000009;
    }
    return tot;
}
long long answer()
{
    if(n==5) return pow(k,n)-2;
    dp[0]=1;
    for(int i=1;i<5;i++) dp[i]=dp[i-1]*k;
    dp[5]=dp[4]*k-(long long)2;
    dp[6]=(dp[5]*k-2*k)%(long long)1000000009;
    for(int i=7;i<=n;i++)
    {
        dp[i]=k*dp[i-1]-dp[i-5]*(long long)2+dp[i-7];
        dp[i]%=(long long)1000000009;
        if(dp[i]<0) dp[i]+=1000000009;
    }
    return dp[n];
}
int main()
{
    scanf("%lld %lld",&n,&k);
    int k=answer();
    if(k<0) k=k+1000000009;
    printf("%d",k%1000000009);
}