CodingPractice/2466.c at main · kimhedol00/CodingPractice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>

int countGoodStrings(int low, int high, int zero, int one) {
    const int MOD = 1000000007;
    int DP[high + 1];
    int
    ans = 0;
    DP[0] = 1;
    for(int i = 1; i <= high; i++) {
        DP[i] = ((i >= zero ? DP[i - zero] : 0) + (i >= one ? DP[i - one] : 0)) % MOD;
        if(i >= low && i <= high)
            ans = (ans + DP[i]) % MOD;
    }
    return ans;
}

/*
Best Solution
int countGoodStrings(int low, int high, int zero, int one){
    long long ans[high + 1];
    ans[0] = 1;
    int append0, append1, mod = 1000000007;
    for(int i = 1;i <= high;i++){
        append0 = i >= zero ? ans[i - zero] : 0;
        append1 = i >= one ? ans[i - one] : 0;
        ans[i] = append0 + append1;
        ans[i] %= mod;
    }long long ret = 0;
    for(int i = low;i <= high;i++){
        ret += ans[i];
        ret %= mod;
    }return ret;

}
*/