앳코더90 - 008 - AtCounter（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_h

008 - AtCounter（★4）

 

문제를 읽어보자마자 이건 dp 라는 생각이들었다.

100000 크기의 문자열이 주어졌을때 이 안에 atcoder가 얼마나 들어있는지 개수를 세라는것이다.

 

핵심로직은 바로 떠올랐지만 구현하는데 어려움을 겪었다.

cache[i][j]  i를 index j를 atcoder의 index로 잡고 저장하는값은 개수이다.

핵심은 a가 나왔을때 이를 다음 a와 t로 보내주는것이다.

이는 코드에서 구현되어있다. 그럼 최종적으로 완성된 atcoder가 모여있는 경우의수를 뽑아낼수있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const ll INF = 100000000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

int N;
int cache[100002][8];
string s;
char atcoder[7] = { 'a','t','c','o','d','e','r' };

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    cin >> s;

    cache[0][0] = 1;

    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j <= 7; j++)
        {
            cache[i + 1][j] += cache[i][j];
            if (j == 7)
                break;
            if (atcoder[j] == s[i])
                cache[i + 1][j + 1] += cache[i][j];
        }
        for (int j = 0; j <= 7; j++) 
            cache[i + 1][j] %= MOD;

    }

    cout << cache[s.size()][7];

    return 0;

}