BOJ 14437번 준오는 심술쟁이!!

https://www.acmicpc.net/problem/14437

정수 S 와 문자열 str 가 입력으로 주어진다.

S <= 3000, len(str) <= 3000

1. 임의로 문자열의 한 문자를 골라서 k(1<=k<=25)만큼 이동시킨다.(a를 3 이동 시키면 d, z를 1 이동시키면 a)

2. 한번 이동했던 문자는 다시 이동시키지 않는다. k의 합이 S가 될 때까지 1번을 반복했을 때 만들어 질 수 있는 문자열의

가짓수를 구하는 문제이다. 

(단, 25*len(str) < S 인 경우는 주어지지 않는다. 즉, 모든문자를 최대한 많이 이동시켜도 S만큼 안되는경우)

그니까 문자열 str 가 있다고 하면 str[0] 을 얼만큼 이동시킬지 정하고,

str[1] 을 얼만큼 이동시킬지 정하고 ..... str[len(str)-1] 를 얼만큼 이동시킬지 정하는 것이다.

처음에 나는

go(pos, s, k) = go(pos, s+1, k+1) + go(pos+1, s, 0) 

와 같은 식으로 재귀로 구현했는데, dp[i][j][k] 로 하여 O(slk) (s <= 3000, l <= 3000, k <= 25) 로 했었는데

이건 2억이 넘어서 시간초과가 난다.

사실 저 위에 점화식을 풀어보면

go(i, j, k) = go(i, j+1, k+1) + go(i+1, j, 0) 인데

go(i, j+1, k+1) 은 다시 go(i, j, k+2) + go(i+1, j+1, 0) 로 나타낼수있기 때문에

go(i, j, k) = go(i, j+2, k+2) + go(i+1, j+1, 0) + go(i+1, j, 0) 이 되며 이걸 계속 반복하면

go(i, j, k) = go(i+1, j+25, 0) + go(i+1, j+24, 0) + ... + go(i+1, j, 0)

와 같은 꼴이 되긴 할 것이다. 아무튼 다시한번 깔끔하게 점화식을 정리해 보면

dp[i][j] = i번째 문자까지 총 j번 이동시켰을 때 나올 수 있는 문자열의 가짓수

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-25] 

라는 점화식이 나오기 때문에

한번 dp[i][j] 를 구했다면 dp[i][j+1] 는 dp[i-1][j+1] + dp[i-1][j] + ... + dp[i-1][j-24] 이기 때문에

dp[i][j] 에서 앞 뒤만 더하고 빼주면 O(1)에 구할 수 있다. 

그러므로 O(sl) 에 답을 구할 수가 있다.

#include <bits/stdc++.h>
#include <map>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll dp[3003][3003];
int S,N;
string str;
int main() {
    cin >> S >> str;
    N = (int)str.size();
    dp[0][0] = 1;
    for(int i = 1 ; i <= N; i++){
        ll sum = 0;
        for(int j = 0 ; j <= S; j++){
            sum = (sum + dp[i-1][j]) % mod;
            if(j > 25) sum = (sum - dp[i-1][j-26] + mod) % mod;
            dp[i][j] = sum;
        }
    }
    cout << dp[N][S];
    return 0;
}