14437 준오는 심술쟁이!!

 

욱제가 준오보고 심술쟁이라 한 줄 알았는데 준오가 준오보고 심술쟁이라 했네

 

하지만 모르겠다. 

 

경우의 수 찾는 거라 s가 6이면 (4, 1, 1) + (3, 2, 1) 이런 경우 다 더하면 나올 것 같은데 저걸 어떻게 구할지 모르겠다.. 어렵다... 

 

 

---

 

으악 준오! 넘 어렵다..

 

식을 도저히 어떻게 세워야 할지 몰라서 다른 사람 코드를 보고 풀었다.

 

dp 문제였음.. ㅜ_____ㅜ dp 쏘 핫

 

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+1]은 dp[i-1][j+1] + dp[i-1][j] + .. + dp[i-1][j-24] 이기 때문에

 

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

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 dp[3003][3003];

int     main()
{
    int s;
    string str;

    cin >> s >> str;

    dp[0][0] = 1;
    for (int i = 1; i <= str.size(); i++)
    {
        i64 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[str.size()][s];

    return 0;
}