8028 : 주사위 조합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
주사위를 하나 던지면 $1$부터 $6$까지의 눈이 나옵니다.
주사위를 여러 번 던져서 나온 눈의 합이 정확히 $N$이 되는 경우의 수를 구하는 프로그램을 작성하십시오.
단, 주사위를 던지는 순서가 다르면 다른 경우로 취급합니다.
[제약 조건]
• $1 \le N \le 10^6$
주사위를 여러 번 던져서 나온 눈의 합이 정확히 $N$이 되는 경우의 수를 구하는 프로그램을 작성하십시오.
단, 주사위를 던지는 순서가 다르면 다른 경우로 취급합니다.
[제약 조건]
• $1 \le N \le 10^6$
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
출력 설명
눈의 합이 $N$이 되는 경우의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
$dp[i]$를 합이 $i$가 되는 경우의 수라고 하면, 점화식 $dp[i] = \sum_{j=1}^{6} dp[i-j]$ (단, $i-j \ge 0$, $dp[0]=1$)이 성립합니다.
동적 계획법을 통해 $O(N)$ 시간에 해결할 수 있습니다.
동적 계획법을 통해 $O(N)$ 시간에 해결할 수 있습니다.