백준 15588 : Stamp Painting

문제 링크

solved.ac에는 플래티넘 5라고 나왔지만, 많이 어려운 문제였다.

문제에서는 n 개의 배열을 m 개의 색깔을 이용해서 채우는 경우의 수를 물어보는데, 이때 색깔은 k의 길이를 가진 도장을 통해서만 채울 수 있다. 색깔을 덮어쓰는 것도 가능하다.

dp를 통해 해결하였다.

예제를 그려본 결과 순서를 적절히 배치하면 k의 길이를 가진 스탬프를 통해 i까지 칠했다고 하면 내가 원하는 대로 1~k까지 색깔을 칠할 수 있다는 것을 깨달았다. 하지만 색깔은 중복해서 선택이 가능하기 때문에, 사실상 내가 원하는 대로 색깔을 칠할 수 있다. 그렇기에 이 문제를 중복순열 문제로 생각할 수도 있지만, 예제를 보면 중복순열의 경우인 2^3 = 8 이 아닌 6인 것을 알 수 있고, 이때 빠진 것은 ABA와 BAB 두 가지라는 것을 알 수 있다.

여기서 도장을 찍을 때 가장 마지막에 찍히는 도장이 있을 것이다. 이는 다른 도장으로 덮을 수 없기 때문에, k 길이만큼 똑같은 색깔로 칠해질 것이고, 다른 색들은 이 도장 이전에 찍히면서 원하는 대로 색을 칠할 수 있다.

따라서 문제는 n 개의 배열을 m 개의 색깔을 이용해서 채우되, 최소 k 길이의 연속해서 같은 색을 가지는 구간이 있는 경우의 수를 구하는 것으로 바뀐다.

이것은 dp를 통해서 구할 수 있는데, 전체 경우에서 연속하는 구간의 길이가 최대 k-1인 경우에 대해서 구한다.

1n의 격자를 11 ~ 1*(k-1)의 격자로 채우는 경우의 수를 구하는 것과 비슷하게 구할 수 있고, dp 식은

dp[i] := dp[i] + (m-1)*(dp[max(0,i-k+1)] + ... + dp[i-1])

로 나타낼 수 있고, 초기조건은 dp[0] ~ dp[k-2] = m이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int mod = 1e9+7;

int n,m,k;
vector<ll> dp;
vector<ll> sum;
int cnt = 0;

//a^b % mod
ll power(int x,int p)
{
    ll ret = 1;
    ll pow = x;

    for(int i = 0;i<28;i++)
    {
        if((p & (1<<i)) != 0)
        {
            ret *= pow;
            ret %= mod;
        }
        pow *= pow;
        pow %= mod;
    }

    return ret;
}

int main()
{
    cin>>n>>m>>k;

    dp = vector<ll>(n,0);
    sum = vector<ll>(n,0);

    for(int i = 0;i<k-1;i++)
    {
        dp[i] = m;
    }
    sum[0] = dp[0];
    for(int i = 1;i<n;i++)
    {
        dp[i] += (m-1) * (sum[i-1] - (i - k < 0 ? 0 : sum[i-k]));
        dp[i] %= mod;
        if(dp[i] < 0) dp[i] += mod;

        sum[i] = sum[i-1] + dp[i];
        sum[i] %= mod;
    } 

    ll ans = power(m,n) - dp[n-1] + mod;
    
    cout<<ans % mod;
    
}