출처: 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 )
'CSES' 카테고리의 다른 글
CSES 2. Subarray Divisibility (1662) (0) | 2019.10.09 |
---|---|
CSES 2. Subarray Sums II (1661) (0) | 2019.10.09 |
CSES 8. Minimal Rotation (1110) (0) | 2019.10.09 |
CSES 2. Maximum Subarray Sum II (1644) (0) | 2019.10.08 |
CSES 2. Movie Festival II (1632) (0) | 2019.10.07 |