2922번: 즐거운 단어

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


$O(l)$

전체 - L을 포함하지 않는 개수를 구해보자.
dp 상태를 자음 1개, 2개 연속 모음 1개 2개 연속 네 가지를 잡아 놓고 설계한다.
dp[i][자음 1개]=(dp[i-1][모음 1개] + dp[i-1][모음 2개]) * ('_'라면 가능한 자음 수 아니면 1)
dp[i][자음 2개]=(dp[i-1][자음 1개]*('_'라면 가능한 자음 수 아니면 1)
모음에 대해서도 비슷한 방법으로 정의해서 푼다.

#include<stdio.h>
typedef long long ll;
ll dp[101][4];
char str[102];
ll f(int x) {
    int i;
    for (i = 1; str[i]; i++) {
        dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = 0;
        if (str[i] == 'A' || str[i] == 'E' || str[i] == 'I' || str[i] == 'O' || str[i] == 'U' || str[i] == '_')
            dp[i][0] = (dp[i - 1][2] + dp[i - 1][3])*(str[i] == '_' ? 5 : 1),
            dp[i][1] = (dp[i - 1][0])*(str[i] == '_' ? 5 : 1);
        if (str[i] != 'A'&&str[i] != 'E'&&str[i] != 'I'&&str[i] != 'O'&&str[i] != 'U')
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1])*(str[i] == '_' ? 21 - x : 1),
            dp[i][3] = (dp[i - 1][2])*(str[i] == '_' ? 21 - x : 1);
        if (x && str[i] == 'L') dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = 0;
    }
    return dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3];
}
int main() {
    scanf("%s", str + 1);
    dp[0][1] = dp[0][3] = 1;
    printf("%lld", f(0) - f(1));
    return 0;
}