CSES 3. Dice Combinations (1633)

출처: https://cses.fi/problemset/task/1633

---

문제 설명

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

• 1+1+1 
• 1+2 
• 2+1 
• 3

입력  

The only input line has an integer n.

출력 

Print the number of ways modulo 10^9+7.

입력 예

3

출력 예

4

제약조건

1 <= n <= 10^6

---

문제 풀이 

주사위를 한번 던져서 나올 수 있는 수는 1~6까지 6가지 경우가 있으므로, 어떤 수 N을 만들기 위해서, 그 전까지 나왔던 경우의 수 (N-1) ~ (N-6)까지 합이 N을 만들 수 있는 경우의 수가 된다.

초기 조건으로 0~5까지 6개의 경우를 입력하고, 6 이상인 경우는 더해서 modulo 연산을 하고,  N이 1~5 인 경우는 초기 조건에서 출력한다.

프로그램 내용

...
    vector<long> dp(6, 0);

    /// dp build up n < 6,
    dp[0] = 1; /// init
    dp[1] = 1;  /// dp[0]
    dp[2] = 2;  /// dp[0] + dp[1]
    dp[3] = 4;  /// dp[0] + dp[1] + dp[2]
    dp[4] = 8;  /// dp[0] + dp[1] + dp[2] + dp[3]
    dp[5] = 16; /// dp[0] + dp[1] + dp[2] + dp[3] + dp[4]

    for (int i = 6; i <= n; i++)
        dp[i] = (dp[i-6] + dp[i-5] + dp[i-4] + dp[i-3] + dp[i-2] + dp[i-1]) % 1000000007; 

...

 

Dynamic Programming ( link )